[백준][C++] 13305 주유소

13305. 주유소

13305번: 주유소

문제 풀이

GitHub - minyoung529/AlgorithmStudy: 여러 알고리즘 문제를 푸는 저장소입니다.

 

또 작은 실수 때문에 한참을 고민한 그리디 문제...

 

알고리즘을 생각하기까지는 오랜 시간이 걸리지 않았지만, 생각한 알고리즘을 코드로 옮기는 데에 문제가 생겼다. 알고리즘 단계를 완벽하게 글로 적었어야 했는데... 나의 알량한 머리를 믿다가 쓰지 않은 조건문 하나에 오랜 시간을 헤맸다.

 

전체적인 알고리즘은 이렇다.

열심히 그려왔다 ㅎ_ㅎ

 

정리하자면, 당장 기름이 급하다면 다음 도시로 갈 때까지의 기름을 넣는다. 그때, 다음, 다다음... 주유소와 가격 비교를 해서 현재 주유소보다 적은 가격을 가진 주유소까지 갈 거리(Km)를 현재 도시에서 미리 기름(L)을 넣는다.

 

코드로 보자면...

 

for (int i = 0; i < len - 1; i++)
{
    int buyCount = 0;

    // 당장 기름이 없으면 다음 거리까지 충전
    while (curOil + buyCount < distances[i])
        buyCount++;

    // 미리 충전을 해놓은 상태에서 굳이 더 저렴한 가격을 찾을 필요 없으므로
    // 미리 충전을 해놓지 않았다면...
    if (buyCount != 0)
    {
        for (int j = i + 1; j < len - 1; j++)
        {
            // 가장 금액이 적은 주유소가 나올 때까지
            // N리터 충전
            if (costs[i] <= costs[j])
                buyCount += distances[j];

            // 내가 한 실수다... break 빼먹기...
            else break;
        }
    }

    cost += ((unsigned long long)costs[i] * buyCount);
    curOil += buyCount;
    curOil -= distances[i];
}

이렇게 된다.

 

전체 코드

 

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

int main()
{
	int len, curOil = 0;
	signed long long cost = 0;
	vector<int> distances;
	vector<int> costs;

	distances.resize(100000);
	costs.resize(100000);

	cin >> len;

	for (int i = 0; i < len - 1; i++)
		cin >> distances[i];

	for (int i = 0; i < len; i++)
		cin >> costs[i];

	for (int i = 0; i < len - 1; i++)
	{
		int buyCount = 0;

		// 당장 기름이 없으면 다음 거리까지 충전
		while (curOil + buyCount < distances[i])
			buyCount++;

		// 충전해놓은 기름이 있었다면
		if (buyCount != 0)
		{
			for (int j = i + 1; j < len - 1; j++)
			{
				// 가장 금액이 적은 주유소가 나올 때까지
				// Nkm 충전
				if (costs[i] <= costs[j])
					buyCount += distances[j];
				
				else break;
			}
		}

		cost += ((unsigned long long)costs[i] * buyCount);
		curOil += buyCount;
		curOil -= distances[i];
	}

	cout << cost;
}

 

사실, unsigned long long도 써본 적이 거의 없는데, 아주 큰 범위가 나올 때마다 자동적으로 쓸 수 있게 익숙해져야겠다.

 

조금 어려웠지만, 할만하고 재미있는 문제였다. 각오해라 그리디... 조건반사처럼 문제를 완벽하게 풀 날을 기대해라...