[BOJ] 13305. 주유소(Python) / Greedy

www.acmicpc.net/problem/13305

13305번: 주유소

문제 이해하는 건 금방이었다. 

그리디(Greedy) 알고리즘으로 접근했다. 

• 그리디하게 for문으로 1번 인덱스부터 현재 위치에서의 주유비와 이전의 주유비와 비교, 최솟값으로 갱신한다.
• 최소 주유비로 거리를 곱한 값을 전체 가격 total 변수에 더해준다.

늘 느끼듯 Greedy나 DP는 발상이 힘들지, 코드는 짧다.

파이썬 코드는 다음과 같다.

 

---

import sys
input = sys.stdin.readline

N = int(input())
info = list(map(int, input().split()))
prices = list(map(int, input().split()))

total = prices[0] * info[0]
MIN = prices[0]     # 최대 가격
for i in range(1, N-1):
    MIN = min(MIN, prices[i])	# 최소 주유비 갱신
    total += MIN * info[i]		# 현재 최소 주유비로 거리 이동
print(total)

---

• 시간 : 160ms / 메모리 : 148424KB
• 고찰 : 매일 빡코, 매일 열공 파이팅.