[백준] 13305 주유소

Posted on | In

이 문제는 그리디 문제이고 나는 이 문제를 풀 수 있어서 너무 좋았다. 별로 어렵지 않은 문제라고 생각할 수도 있겠고 그리디 문제라는걸 알지 못했다면 풀지 못했을 수도 있지만 어쨌든 이 문제를 풀어서 기분이 너무 좋다!

문제 설명

이 문제는 주유소 개수(n), 각 주유소의 1리터당 가격, 주유소 사이의 거리가 주어졌을 때 최소 비용으로 첫 주유소에서 마지막 주유소까지 운행이 가능하냐를 묻는 문제이다. 예를 들자면, 4개의 주유소가 있고 각 주유소의 1리터당 가격이 5, 2, 4, 1 이고, 주유소 사이의 거리는 2, 3, 1 일때 최소 비용은 첫번째 주유소(5)에서 2리터를 사서 5x2=10을 사용하기, 두번째 주유소(2)에서 4리터를 사서 남은 거리를 다 가기, 즉 2x4만큼 사용하기 했을 때 최소 비용이 된다. 즉 18이 최소 비용이다. (백준 이미지)

이미지

문제 풀이

그럼 이 문제를 풀기 위해서는 어떻게 해야 하는가? 그리디 문제이기 때문에 내게 주어진 그 순간에서 최선을 찾으면 된다. (미래는 고려하지 않아도 된다) 따라서 내가 첫번째 주유소를 갔을 때에 최선은 첫번째 주유소에서 두번째 주유소까지 갈 수 있는 만큼 사면 되는 것이다. 그리고 두번째 주유소에 도달하면, 첫번째 주유소와 두번째 주유소 중 더 가격이 낮은 곳을 택해서 거기서 세번째 주유소까지 갈 만큼 사면 된다. 따라서 첫번째 주유소에서 세번째 주유소까지 갈 때에는 첫번째 주유소에서 다 사는 방법과 첫번째 두번째 나눠서 사는 두 방법이 생기게 된다. 최소 비용은 계속 가면서 판단하면 된다. 네번째 주유소에 갈 때도, 첫번째 두번째 세번째 주유소 중에서 제일 가격이 낮은 주유소에서 다음 주유소 갈 만큼을 사면 된다. 이걸 주유소가 끝날 때까지 반복해 주면 된다.

이 문제는 타입에서 차별성을 뒀는데, 단순히 int 범위에서만 가능하도록 하면 58점밖에 나오지 않는다. long long 타입을 써야 하는데 나는 long long 타입도 불안해서 그냥 unsigned long long을 썼다. 따라서 scanf안도 %lld가 아니라 %llu를 사용했고, unsigned long long min 또한 범위 내 가장 큰 값을 주었다. 나는 처음에 unsigned long long을 썼는데도 58점이 나와서 왜 그런가 했는데, min 값이 충분히 크지 않아서 잘 작동하지 않았던 것이다. min값을 범위 내 가장 큰 값을 주면 어렵지 않게 해결할 수 있는 문제가 된다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <cstdio>

int main(){
    int n;
    scanf("%d", &n);
    unsigned long long r[100001]; 
    unsigned long long h[100001];
    for(int i=0;i<n-1;i++) scanf("%llu", &r[i]);
    for(int i=0;i<n;i++) scanf("%llu", &h[i]);

    unsigned long long sum=0, min=1000000000;
    for(int i=0;i<n;i++){ //h 기준 iter
        if(h[i]<min){
            min=h[i];
        }
        sum+=min*r[i];
    }

    printf("%llu\n", sum);
}

문제 맞아서 기분이 좋았다. 맞았습니다