[백준] 13305 주유소(Python)

해당 게시글에서는 [백준] 13305 주유소 문제를 해설하고 Python을 이용하여 풀고자 한다.

💡 문제 풀이

13305번 문제는 Greedy에 대한 문제로 각 단계마다 최적의 상황을 선택하여 최종적인 해답에 도달하는 방식의 알고리즘이다.

 

이 문제에서는 제일 오른쪽 지점에 도달했을 때 기름의 비용이 최소가 되는 것을 원하므로, 각 도시를 지나기 위해 기름의 비용을 계산할 때 상황에 따라 작은 값을 이용하여 계산해야 한다.

 

만약 앞 도시의 기름의 비용이 뒷 도시의 기름의 비용보다 싸다면, 앞 도시에서 주유하는 것이 비용이 적게 드므로 뒷 도시에서 주유하는 것이 아닌 앞 도시에서 미리 주유해야 한다.

 

따라서 왼쪽에서 오른쪽으로 순차적으로 이동하면서 최소 비용을 저장하여 (최소 비용)*(각 도시 사이 거리)를 더해줘야 한다.

아래 코드는 각 도시를 이동할 때 최소 비용인지 확인하고 최소 비용이라면, 이후에 주유 비용을 계산할 때 사용하기 위해 최소값을 저장하는 부분이다.

if cost[i] < cost[cur]:
    cur = i

위에서 계산한 최소 비용을 통해 각 도시를 지나칠 때마다 (최소 비용)*(도시 사이 거리)를 최종 비용을 저장하는 변수에 더한다.

result += cost[cur]*len[i]

 

📂 코드

• cur: 최소 비용이 되는 도시의 index를 저장

N = int(input()) # 도시의 개수
len = list(map(int, input().split())) # 각 도시 사이 거리
cost = list(map(int, input().split())) # 주유 비용

cur = 0 # 최적(최소)의 비용 저장
result = 0 # 주유 비용 합계
for i in range(0, N-1):
    if cost[i] < cost[cur]:
        cur = i
    result += cost[cur]*len[i]
print(result)