[백준 13305 파이썬] 주유소 (실버4, 그리디)

알고리즘 유형 : 그리디
풀이 참고 없이 스스로 풀었나요? : O

https://www.acmicpc.net/problem/13305

소스 코드(파이썬)

import sys
input = sys.stdin.readline

N = int(input())
d = list(map(int, input().split()))
cost = list(map(int, input().split()))

result = cost[0] * d[0]
prev = cost[0]

for gate in range(1, N-1):
    if cost[gate] < prev:
        prev = cost[gate]
    result += prev * d[gate]

print(result)

풀이 요약

1. 한 주유소에서, 그 다음 주유소까지 갈 때 필요한 기름보다 더 많은 양을 사서 그 후에도 더 쓸 수 있다. 그렇다면 저렴한 주유소에서 기름을 사서, 그 뒤에 있는 그 보다 비싼 주유소에서 쓸 기름을 대신해주는 원리가 최선인 것으로 보인다.

2. 현재 주유소에 대해, 일단 저장되어 있는(prev) 현재 주유소 기름 값으로 다음 주유소까지 거리만큼 기름을 산다.(기름 값 * 거리) 다음 주유소의 기름 값이 현재 주유소보다 낮다면, prev를 다음 주유소 기름 값으로 갱신해주고, 아니라면 현재 주유소 기름 값을 다음 인덱스로 그대로 들고간다(prev 미갱신). 여기까지를 마지막-1 인덱스까지 반복 진행해준다.

배운 점, 부족했던 점

• 최선의 선택을 생각해내는 데 조금 애먹었다. 기름 값과 거리를 튜플로 담는다던지, 주유소를 오름차순으로 정렬한다던지 뻘짓을 많이 했다. 한 40분 쯤 걸린 것 같은데 문제 해결 능력이 아직 많이 다듬어지지 않은 것 같다. 문제 풀이 양을 좀 더 늘리면 될 것 같다.