13305. 주유소

13305 문제 보기

접근 방식

그리디 기본 문제

최종 코드

• 가장 가격이 저렴한 주유소를 찾아 주유하기
• 최소 비용을 구해야 함

import sys
input = sys.stdin.readline

N = int(input().rstrip()) # 도시의 개수
dist = list(map(int, input().rstrip().split())) # 인접한 두 도시를 연결하는 도로의 길이(N-1개)
cost = list(map(int, input().rstrip().split())) # 주유소의 리터 당 가격

min_cost = cost[0]
total = 0

for i in range(N-1):
  if min_cost > cost[i]:
    min_cost = cost[i]
  total += min_cost * dist[i]
  # print(i, min_cost, dist[i], total)

print(total)

배운점

그리디 문제를 풀이할 때
1. 탐욕적으로 현재 단계에서 가장 좋은 것 고름
2. 가장 좋아보이는 것의 선택을 연속적으로 해도 최적의 해를 구할 수 있는지 검토