Baekjoon 13305 (주유소)

Baekjoon 13305, 백준 13305 문제의 본인 풀이입니다!
문제는 아래의 링크에서 확인할 수 있습니다.
문제보기

#include <cstdio>
#define MAX_N 100000

int N, road[MAX_N+3], gas[MAX_N+3];

int main() {
    // Initialization: save inputs
    scanf("%d", &N);
    for(int i = 0; i < N-1; i++) {
        scanf("%d", &road[i]);
    }
    for(int i = 0; i < N; i++) {
        scanf("%d", &gas[i]);
    }

    long long totalMoney = 0;     // total money
    int gasVal = gas[0];   // lowest gas value until now (Greedy Algorithm)
    int roadNum = 0;       // road number (0 to N-1)
    while(true) {
        totalMoney += (long long)gasVal * road[roadNum];
        roadNum++;
        if(gas[roadNum] < gasVal) {
            // Greedy: Use the new gas value from now on
            gasVal = gas[roadNum];
        }
        if(roadNum == N) {
            // Finish Algorithm
            break;
        }
    }

    printf("%lld\n", totalMoney);

}

본 문제는 그리디 알고리즘 (Greedy Algorithm) 을 사용하는 문제였다.

예전부터 언급해왔던 ‘백준 단계별로 풀어보기’의 치명적인 단점은 단계 명에서 어떠한 알고리즘을 사용해야 하는지 친절하게 알려준다는 점이다. 사실상 거대한 힌트를 얻고 들어가는 것이니…
본 문제는 자체로 어려운 문제는 아니였고, 그리디 알고리즘을 사용하라는 힌트를 받으면 더 쉬워지는 문제였다. 이 정도라면 힌트 없이도 무난하게 그리디로 풀겠다는 감을 잡을 수 있지 않을까?

아이디어는 여태까지 나온 최고 저렴한 기름으로 최대한 많이 이동하는 것 이다. 별 다른 증명 없이 꽤 깔끔하게 이 사실이 받아들여진다.

그럼에도 불구하고 세 번이나 틀렸습니다 를 마주했는데, 범인은 int의 자료형 초과였다. 변수에서, 그리고 형변환 시에 unsigned long을 명시해 주니 바로 통과할 수 있었다. 롱태식이 오랜만이다!