문제 링크: https://www.acmicpc.net/problem/13305

문제 상황

• 수평방향의 일직선 도로 위에 있는 \(N\)개의 도시가 있을때, 제일 왼쪽의 도시에서 가장 오른쪽의 도시로 자동차를 이용해 이동한다.
• 도시 간 도로의 길이(\(km\))는 서로 다를 수 있으며, 각 도시마다 하나씩 주유소가 있고 주유소의 리터당 가격(원)은 다를 수 있다.
• 출발 전 자동차는 기름이 없어서 주유 후 출발하며, 기름통의 크기는 무제한이다.
• 이 차는 \(1km\) 주행마다 \(1ℓ\)의 기름을 사용한다.

각 도시의 주유소 기름의 리터당 가격과 도시간 거리가 주어질 때, 필요한 최소의 비용을 구하라.

입력

Line 1: 도시의 개수를 나타내는 정수 \(N (2 ≤ N ≤ 100,000)\)

Line 2: 도시 간 도로의 길이 (제일 왼쪽 도로부터 순서대로 \(N-1\)개. 도로의 길이는 자연수이며, 도로 전체의 길이는 \(1\)이상 \(1,000,000,000\) 이하)

Line 3: 주유소의 리터당 가격 (제일 왼쪽 도시부터 순서대로 \(N\)개, \(1\) 이상 \(1,000,000,000\) 이하의 자연수)

출력

제일 왼쪽도시에서 제일 오른쪽 도시로 가는 최소 비용을 출력한다.

C99로 구현하였다.

1. 예시 연구

문제의 예시로 제시된 케이스를 살펴보며 문제 해결 전략을 찾아보자. 편의상 왼쪽부터 1번도시, 2번도시, 3번도시, 4번도시라 부르겠다.

1. 1번도시에서 6리터 몰빵 후 출발하는 경우 (\(30\)원, 이후 주유가 필요 없다.)
2. 1번도시에서 2리터만 넣고 가는 경우. (\(5×2=10\)원)
   1. 2번도시에서 4리터를 사는 경우 (\(10+2×4=18\)원, 이후 주유가 필요없다.)
   2. 2번도시에서 3리터만 사는 경우 (\(10+2×3=16\)원)
      • 3번도시에서 1리터를 사야한다. (\(16+4×1=20\)원)

모든 케이스를 조사하였고, 18원이 최소비용이라는 사실을 알 수 있었다. 그런데… 이걸 일일히 조사해봐야만 알 수 있을까?

우리가 컴퓨터 없이 문제를 풀었다면 어떻게 풀었을까. 우선 무작정 시작해보자.

(1번도시) 음 우선 \(2km\)는 가야하니까 \(5\)원이어도 사야지. (\(5×2=10\)원)

(2번도시) \(2\)원이니까 아까보다 싸졌네. 우선 \(3km\) 가야하니까 \(3ℓ\) 사야지. (\(10+2×3=16\)원)

(3번도시) \(4\)원이면 아까보다 많이 비싸네. 아까 \(2\)원일때 사면 좋았는데

저렇게 후회하는거 보면 다음 도시까지 가기 위한 최소한의 기름만 사는 전략은 좋은 전략은 아닌 거 같다. 그렇다고 처음에 몰빵하는 전략도 아니다. 그럼 최소값을 검색해서 그때 몰빵을 할까? 최소값이 마지막에 나오는 최악의 경우는? 그럼 그다음 최소값이라도 확인하나? 10만개의 도시와 9만 9999개의 도로의 길이가 주어질 예정이다. 시간복잡도…를 생각하면 좋은 생각이 아닌거 같다.

곰곰히 생각해보면 운전자는 뒤늦게 후회를 하겠지만 우리는 실제 주유를 하고 운전을 하는 것이 아니니까 알 바가 아니다(?) 이미 3번도시에 도착한 후 후회했지만, 그제서야 2번도시에서 기름을 사면 어떨까. 실제 주행 중이라면 물리적 제약으로 불가능하지만 우리는 컴퓨터 앞에 앉아서 계산할 뿐이다. 여태까지 거쳐온 주유소들 중 최저가를 기억했다 그때그때 사면 되지 않겠나! 주유소계의 다나와 오피넷

(3번도시) \(4\)원이면 아까보다 많이 비싸네. 아까 \(2\)원일때 사는게 싼거니까 2번도시에서 \(1ℓ\) 더 샀던 걸로 치자. (\(16+2×1=18\)원)

(4번도시) 덕분에 최소 비용으로 잘 도착했다. (운행이 끝났으므로 더 이상 주유가 필요 없다.)

운전자는 울면서 비싼 기름을 사서 주유했고 다음 도시 주유소가 싼 걸보고 배가 아플거다. 하지만 우리는 결국 최소비용을 잘 계산했으니 상관없다. 꽤 괜찮은 전략인 것 같다.

2. 전략 구현

여태까지 거쳐온 주유소들 중 최저가를 기억했다 그때그때 사면 되지 않겠나!

앞서 이야기 해본 전략을 구현해보자.

int temp,min=1e9,sum=0,road[1e9];

for(int i=0;i<N-1;++i)
    scanf("%d",road+i);
    
for(int i=0;i<N-1;++i){
    scanf("%d",&temp);
    if(min>temp) min=temp;
    sum+=min*road[i];
}
scanf("%d",&temp);

새로운 주유소를 지날때마다 주유소 최저가를 갱신 해준 후 그 최저가로 다음 주행 거리만큼 구매하고 있어서, 최저의 공간 비용으로 최소비용을 구할 수 있게 되었다.

주유소 가격은 실시간으로 처리 했지만, 도로 길이는 저장해야 했다. 도로길이를 먼저 한꺼번에 받아야 주유소 가격을 주기 때문이다. 또 마지막 도시에선 구매가 필요 없으나 입력은 받아야 하니 반복을 한번 덜하고 빠져나온후 마지막 입력을 받기로 했다. 받아서 버린다

이게 끝이다. 생각보다 코드도, 글도 짧다. 입출력까지 모두 구현하고 정리해보자.

int N,temp,min=1e9,sum=0,*road;
    
scanf("%d",&N);
road=(int*)malloc((--N)*sizeof(int));
    
for(int i=0;i<N;++i)
    scanf("%d",road+i);
for(int i=0;i<N;++i){
    scanf("%d",&temp);
    if(min>temp) min=temp;
    sum+=min*road[i];
}
scanf("%d",&temp);
    
printf("%d",sum);
free(road);

이번에도 역시 필요한 road의 사이즈는 N에 따라 가변적이니 동적 메모리 할당을 이용하였다. 한편 N이 필요한 경우는

1. 동적 메모리 할당시 공간의 크기 계산
2. 도로의 길이를 받을 때 반복문
3. 주유소 가격을 받을 때 반복문

가 전부이다. 그리고 세가지 경우 모두 다 N-1을 필요로 하기 때문에 그냥 받자마자 --N;을 실행했다.

3. Greedy Algorithm : 탐욕법

나무위키: 그리디 알고리즘

그리디 알고리즘(욕심쟁이 알고리즘, Greedy Algorithm)이란 “매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자” 라는 모토를 가지는 알고리즘 설계 기법이다.

단, 그리디 알고리즘을 사용하면 매 선택이 그 순간에 대해서는 최적이지만 그걸 종합적으로 봤을 땐 최적이라는 보장은 절대 없다는 것을 명심해야 한다.

그리디 알고리즘은 - 탐욕 선택 속성(greedy choice property) - 최적 부분 구조(optimal substructure) 특성을 가지는 문제들을 해결하는데 강점이 있다. 즉, 한번의 선택이 다음 선택에는 전혀 무관한 값이여야 하며 매 순간의 최적해가 문제에 대한 최적해여야 한다는 의미이다.

역시 이번에도 조금만 긁어와서 적당히 마무리 지으려 했지만 내가 하고 싶은 말을 다 긁어왔다.

여태까지 동적계획법으로 풀었던 문제들은 탐색 중 최적경로라 보장할 수 있는 경로를 바로바로 찾아낼 수 없는 상황이었기 때문에 다양한 방법으로 일일히 조사해왔던 것이다.

이 문제는 3번도시에 와서도 2번도시에서 기름을 사는 행위(?)가 가능 했기 때문에 탐색 중 그때그때 최적해를 찾아나갈 수 있었다. 저런 방식을 시도할 수 없는 문제 형태가 주어진다면… Greedy Algorithm을 사용이야 할 수는 있지만 최적해를 보장하지 않는다. Greedy Algorithm을 사용하려면, 문제가 상기 서술한 조건에 부합하는지, 아니면 최적해가 아니여도 상관 없는지 확인해야 하겠다.

보통 그래서 Greedy Algorithm으로 풀리는 문제들은 제약조건이 많다. 그렇다고 무조건 그리디로 풀다 피본다.

4. 최종 코드

4-1. gas_station_final.c

main 함수에 넣고, 필요한 헤더를 포함시켜 제출하자.

#include <stdio.h>
#include <malloc.h>

int main(int argc, const char* argv[]){
    int N,temp,min=1e9,sum=0,*road;
    
    scanf("%d",&N);
    road=(int*)malloc((--N)*sizeof(int));
    
    for(int i=0;i<N;++i)
    	scanf("%d",road+i);
    for(int i=0;i<N;++i){
    	scanf("%d",&temp);
        if(min>temp) min=temp;
        sum+=1LL*min*road[i];
    }
    scanf("%d",&temp);
    
    printf("%d",sum);
    free(road);
    return 0;
}

제출 소스 확인하기

분명 문제에서 주어진 예시 테스트 케이스는 맞았는데, ‘채점 중…(??%)’ 채점 중 표시도 없이 ‘틀렸습니다’가 떴다.

문제를 다시 읽어보고 그제야 깨닫는다. 항상 당연하다고 생각한게 당연한지 확인해야 한다. 배열 인덱스… 오버플로우…

리터 당 기름가격이 최대 10억이니(?) 최악의 경우 그걸 9만 9999번 더할텐데 당연히 int 범위(\(2^{31}-1\))에서 해결이 불가능하다. 그래도 다행히 long long 범위에 들어간다.

???: 오버플로우 때문에 틀린 것 뿐이야

항상 확인해주자.

4-2. gas_station_final_final.c

#include <stdio.h>
#include <malloc.h>

int main(int argc, const char* argv[]){
    int N,temp,min=1e9,*road;
    long long sum=0LL;
    
    scanf("%d",&N);
    road=(int*)malloc((--N)*sizeof(int));
    
    for(int i=0;i<N;++i)
        scanf("%d",road+i);
    for(int i=0;i<N;++i){
        scanf("%d",&temp);
        if(min>temp) min=temp;
        sum+=1LL*min*road[i];
    }
    scanf("%d",&temp);
    
    printf("%lld",sum);
    free(road);
    return 0;
}

다행히 gas_station_final_final 에서 끝났다. 프로젝트-최종-최종본-수정-확정

제출 소스 확인하기