[Greedy/그리디] 백준 13305 주유소 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

13305번: 주유소

 

 

 

2. 문제 풀이

 최소의 주유비용으로 거리를 완주해야하는 문제입니다.

 

2022.01.26 - [Algorithm] - [Algorithm] 탐욕적인 그리디 알고리즘, 직관적이고 쉬운 문제해결

[Algorithm] 탐욕적인 그리디 알고리즘, 직관적이고 쉬운 문제해결

 지난 주유소 중 가장 싼 가격으로 주유하면 됩니다. 실제로는 한 번 지나가면 이전 주유소로 돌아갈 수 없지만, 프로그래밍 상에서는 '그 주유소에서 주유했다는 셈'치고 계산할 수 있습니다.

 

 

 

3. 코드

import sys
input = sys.stdin.readline

# 입력
N = int(input())
road = list(map(int, input().split()))
cost = list(map(int, input().split()))

# 그리디 알고리즘
min_cost = 1000000001  # 최대 가격
res = 0  # 최소 기름값
for dist, cost in zip(road, cost):
    min_cost = min(min_cost, cost)
    res += min_cost * dist
print(res)

 zip() 함수를 이용해서 거리와 주유소 가격을 1개씩 꺼냅니다. 여태까지 주유소 가격 중에서 가장 싼 가격을 저장하고, 거기서 기름을 충전합니다.

 맨 마지막 도시의 주유소 가격은 어차피 필요가 없으므로, 무시합니다.