그리디 알고리즘 13305번

www.acmicpc.net/problem/13305

13305번: 주유소

import sys

# 입력받기
N = int(sys.stdin.readline())
meter = list(map(int, sys.stdin.readline().split()))
fuel = list(map(int, sys.stdin.readline().split()))

cost = 0
min_fuel = fuel[0]

# 계산
for i in range(N-1):
    if min_fuel >= fuel[i]:
        min_fuel = fuel[i]
    cost = cost + min_fuel*meter[i]

print(cost)

포인트:

  1. 2번째 주유소에 가려면 1번째 주유소에서 그 거리만큼 반드시 주유를 해야한다.

  2. 다음 주유소를 가기위해: 그동안 거쳐온 주유소들(다음 주유소들 제외!)에서의 최소 주유값을 찾아 거리만큼 주유를 한다.

 

느낀점:

문제에 그림도 있어서 어려워보인다는 생각이 먼저 들었는데, 차분히 읽으면서 그림그리다보니 생각보다 어렵지 않았다.