BOJ 13305

Input

표준 입력으로 다음 정보가 주어진다.

첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다.

다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1개의 자연수로 주어진다.

다음 줄에는 주유소의 리터당 가격이 제일 왼쪽 도시부터 순서대로 N개의 자연수로 주어진다.

제일 왼쪽 도시부터 제일 오른쪽 도시까지의 거리는 1이상 1,000,000,000 이하의 자연수이다. 리터당 가격은 1 이상 1,000,000,000 이하의 자연수이다.

import sys
input = sys.stdin.readline

n = int(input().rstrip())
km = list(map(int, input().split()))
p = list(map(int, input().split()))

Greedy

그리디는 일단 현재 상황에서 할 수 있는 최선의 선택을 하고보는 타입이다. 이 문제가 대표적인 예시 같은데,

현재 위치 기준 바로 다음 주유소의 가격이 싸면 일단 간다.
1
2
3
if p[now] > p[now+1]:
ret += p[now] * km[now]
now += 1

비싸면 지금보다는 싼 주유소를 찾을 때까지 계속 찾고, 싼 곳을 찾으면 거기로 이동한다.

else:
  dist = 0
  next = 0
  for next in range(now + 1, n):
    dist += km[next-1]
    if p[now] > p[next]:
      break
  ret += dist * p[now]
  now = next

이 모든 건 도착지 전까지만 해당, 도착지에 도달할 경우 종료해야 한다.
1
while now < n-1:
완전 탐색처럼 가장 싼 곳을 찾아서 움직이면 안 된다. 중간중간에 절약할 수 있는 경우에는 일단 절약하고 봐야 함.