[BaekJoon/백준] 13305번 그리디 알고리즘 | 복습 1회 완료

주유소 문제.

 

처음엔 이걸 동적계획법으로 푸는거 아닌가 했는데, 생각해볼수록 그건 아닌 것 같았다. 방법이 조금 달랐다.

 

어찌저찌, 그리디알고리즘으로 풀 방법을 생각해냈는데.. 결과는 참혹했다.

참담했다

이러한 지옥을 경험한 이유.. 그 문제는 자료형 이였다. 자료형이 문제가 됐다..

 

 

우선, 그리디 알고리즘답게 선택방법은

 

● 기름값이 작은 곳이 나올때까지의 경로까지를 모두 내가 계산(이 지역에서 채움)

 

이거면 풀 수 있따.

 

 

우선

처음 헤맸던 방식의 틀린 코드다..

#include <stdio.h>

int N;
int cost[100000];
int km[99999];
long long total_cost = 0;

int main() {
    
    int cur_cost = 0, i = 0;
    long len = 0;
    int p = 0; // km 이터레이터.
        
    scanf("%d", &N);
    
    for(i = 0; i < N - 1; i++) {
        scanf("%d", &km[i]);
    }
    
    for(i = 0; i < N; i++) {
        scanf("%d", &cost[i]);
    }
    
    cur_cost = cost[0];
    
    // 틀린 이유 : 여기선 len이 쌓이다보니 len*cur_cost가 계산이 안되는거같아서, len을 쌓지않고 바로바로 해주기로 바꿨다.
    
    for(i = 0; i < N ; i++) {

        // 현재 비용값보다 더 작은 비용값의 도시를 찾을때까지, 현재 비용값으로 경로 기름을 채움.
        // N - 1 인덱스는 도착지이므로 무조건 작업(마지막 도시인 N - 1 인덱스의 비용값은 아예 상관없음)
        if(cur_cost > cost[i] || i == N - 1) {

            total_cost += len*cur_cost;
            cur_cost = cost[i];
            len = km[p++]; // 쌓임이 아니라 대입(초기화)

        } else {
            len += km[p++]; // 쌓임
        }
    }
    printf("%ld", total_cost);
}

여기서 틀렸던 부분은 주석으로 설명해놨는데, 비용값이 교체되지 않는 한 도시 간의 거리를 계속해서 len에 더해주었다가 한번에 계산해주는 방식을 사용했기 때문에 total_cost += len*cur_cost 에서 int * int 의 오버플로우가 난 것 같다. 1LL*len*cur_cost 해줘도 소용없었다. 크기가 너무 컸나보다...

 

 

그래서, 도시 간의 거리를 쌓아놨다가 한번에 계산하는 방식 대신에, 매번 차례로 계산해주는 방식으로 바꿨고, total_cost += len*cur_cost를 total_cost += 1LL*len*cur_cost로 바꿔주니 이번엔 문제가 해결되었다. 

 

해결된 풀이

#include <stdio.h>

int N;
int cost[100000];
int km[99999];
long long total_cost = 0;

int main() {
    
    int cur_cost = 0, i = 0;
    int p = 0; // km 이터레이터.
        
    scanf("%d", &N);
    
    for(i = 0; i < N - 1; i++) {
        scanf("%d", &km[i]);
    }
    
    for(i = 0; i < N; i++) {
        scanf("%d", &cost[i]);
    }
    
    cur_cost = cost[0];
    
    for(i = 0; i < N ; i++) {
        
        if(cur_cost > cost[i])
            cur_cost = cost[i];
        
        // 1LL붙여주니 정답. int * int 의 범위를 벗어나서 그런듯. 10억 10억 이렇게될수도있으니.
        total_cost += 1LL*cur_cost*km[p++];
    }
    
    
    printf("%ld", total_cost);
}

자료형.. 생각 잘 해줘야한다.

 

어쨌든 이번 문제의 풀이 방식은 현재 비용값보다 더 작은 비용값의 도시를 찾을때까지, 현재 비용값으로 경로 기름을 모두 채운다는 것.

 

 

 

설명이 필요하신 분은 아래 글을 참고하면 좋을 것 같습니다. 제 풀이와 비슷하십니다.

st-lab.tistory.com/192

[백준] 13305번 : 주유소 - JAVA [자바]

 

---

2021.02.26 복습

다시풀어보았다.

#include <stdio.h>

int N;

int D[99999]; // Distance
int P[100000]; // Price
int C = 1000000001; // Current_Price. 범위 내 가장 큰 수로 초기화.
long long result;

int main() {
    int i;
    
    scanf("%d", &N);
    
    for(i = 0; i < N - 1; i++)
        scanf("%d", &D[i]);
    
    for(i = 0; i < N; i++)
        scanf("%d", &P[i]);
    
    // N - 1번째는 어차피 할 필요 없으므로 i < N - 1.
    // 게다가 이렇게 하는게, 아래에서 식을 일관성있게 진행시킬 수 있음.
    for(int i = 0; i < N - 1; i++) {
        
        if(C > P[i])
            C = P[i];
        
        result += 1LL * C * D[i];
    }
    
    printf("%lld", result);
}

처음 풀었던 것 보다 훨씬 간결하게 푼 것 같다!! 굿!!