[python] BOJ 13305 주유소

백준 13305번 주유소

그리디 알고리즘의 대표적인 문항인 13305번 주유소 문제이다.

 

길게 써져있지만 요약하면, 동그라미안의 숫자는 1L당 가격이고 사이 숫자는 거리를 나타낸 것이다.

각 도시에서는 최소한 다음 도시까지 갈 기름을 구매해야한다. 

즉 도시에서 도시사이의 거리는 기름에 대한 최소 조건이 된다. 직관적으로 가장 싸게 이동하려면, 기름 가격이 비싼 곳에서는 최소 필요 기름만큼만 구매하고 기름 가격이 저렴한 곳에서는 최대한 많이 구매하면 된다.

 

풀이

예시를 한번 가져와보자.

4개의 도시에서 각 도시 사이의 거리는 2 , 3 ,1 이고

각 도시의 L당 기름 값은 5, 2, 4, 1 이다. 사실 문제를 잘 읽으면 알 수 있는것이 마지막 도시의 기름 값은 고려할 필요가 없다.

 

최소 비용이 도출되는 과정을 전개해보자.

즉 핵심은 최소 기름 값을 구해서 각 도시에서 기름 가격을 비교하는 것이다.

코드를 작성해보자.

이 코드로 작성해서 냈더니,  패스가 안뜬다. 

다시 생각해보니까 내가 착각한 부분이 있었다.

5 3 2 1 4 5 8 9 4 1

위와 같은 예시가 있을때, 내가 작성한 코드에서는

최소 기름값이 4 이기때문에

첫번째 도시와 두번째 도시를 지나치면

3 x 5 + 2 x 8 = 31 이다

하지만 최소비용을 계산하면

5 x 5 = 25 이다.

즉 다시 말해서, 다음 도시 기름값과 현재 도시 기름값을 비교하는 알고리즘이 필요한 것이다. 

 

위의 알고리즘은 잘못되었고 수정해야한다.

 

현재 도시와 다음 도시의 기름 값을 비교하면서 도시를 방문해야한다.

 

현재 도시 기름 값 > 다음 도시의 기름 값이라면 두 도시 사이의 거리만큼의 기름만 구매한다.

 

현재 도시 기름 값 = 최저 기름 값이라면, 남은 모든 구간의 거리만큼 기름을 구매한다.

 

현재 도시 기름 값 < 다음 도시의 기름 값이라면, 현재 도시보다 더 싼 값이 있는 다음 도시의 거리까지 기름을 구매한다

5 3 2 1 4 5 8 9 4 1

다시 구해보자.

0. 최저 기름 값은 4 이다.

1. 첫번째 도시에서 5<8 이므로 두번째 거리까지 기름을 구매한다. 또한 아직까지 현재 도시 기름 값은 5로 설정

 ==> 5 x (3+2) = 25

 

2. 두번째 도시에서는 이미 앞에서 구매한 기름을 사용했다. 현재 도시 기름 값은 5로 설정

 

3. 세번째 도시에서는 5<9 이므로  5x1 = 5 

 

4. 네번째 도시에서는 최저 기름 값에 해당하는 도시이므로, 4x4 = 16

 

따라서 25 + 5 + 16 = 46 이다.

 

위의 과정에서 핵심은 현재 도시 기름 값은 더 싼 가격이 나올때까지 가격이 변하지않는다는 것

위와 같이 작성했을 때 답이 나왔다. 

예시로 주어진 케이스에 빠져서 너무 문제를 단순하게 생각했었다.