C++ / 13305 / 주유소 ( 그리디 알고리즘 )

https://www.acmicpc.net/problem/13305

 

문제 요약

 

n개의 마을의 수를 입력받고 각 마을의 리터당 기름의 요금과 마을 사이 거리 ( n - 1 )를 입력 받습니다.

제일 왼쪽 도시에서 제일 오른쪽 도시로 이동하는 최소의 비용을 계산하는 프로그램을 작성해야합니다.

문제 풀이

1. 롱 롱 인티저 로 백터를 만들어서 마을 별 가격과 마을 사이 거리를 입력 받습니다.

2. t 는 가장 싼 가격의 마을의 인덱스 입니다.

3. t에 초기값으로 0을 넣고 마을 횟수  ( n ) 만큼 반복문을 돌립니다.

4. t번째 마을과 i번째 마을의 기름 가격을 비교하여 더 싼 가격을 t에 저장합니다.

5. 다음 마을까지 거리( r[i] 까지) 만큼 기름 가격을 sum에 더합니다. 

6. 마지막 마을의 기름 가격은 의미 없으무로 예외 처리로 break합니다.

 

주의할 점

수를 담을 변수를 그냥 int로 선언시 더 큰 값의 경우의 수를 저장할 수 없기 때문에 롱롱으로 저장하는것을 잊지 말아야 합니다.

마지막 마을의  기름 요금은 어차피 넣을 필요가 없기 때문에 예외 처리도 잊지 말아야 합니다.

 

코드

#include <iostream>
#include <vector>
#include<algorithm>
using namespace std;

typedef long long ll;

ll n, t;
ll sum = 0;
vector<ll> r;
vector<ll> p;
ll a;

int main()
{
	cin >> n;

	for (int i = 0; i < n - 1; i++)
	{
		cin >> a;
		rsum += a;
		r.push_back(a);
	}
	for (int i = 0; i < n; i++)
	{
		cin >> a;
		p.push_back(a);
	}
    
    // 비교할 값의 인덱스 초기값
    //p[t] == 가장 싼 기름 가격
	t = 0;
    
    // 전체 마을 갯수 만큼 반복
	for (int i = 0; i < n; i++)
	{
    	// p[t]의 값과 현재 마을의 기름 값 비교
        // 현재 마을이 더 싸면
		if (p[t] > p[i])
		{
        	// t 값 변경 
			t = i;
		}
		// 마지막 마을의 기름 가격은 의미 없음
		if (i == n - 1)
		{
			break;
		}
		else
		{
			for (int j = 0; j < r[i]; j++)
			{
            	// p[t]의 가격으로 다음 마을 까지 거리 만큼 가격을 더함
				sum += p[t];
			}
		}

	}
	cout << sum;
	return 0;
}

반응형

예제 입력 1

4
2 3 1
5 2 4 1

결과 1

예제 입력

4
3 3 4
1 1 1 1

결과 2