[BOJ][🟡5][백준#10710] 실크로드

문제 출처

BAEKJOON Online Judge #10710

문제

과거 카자흐스탄에는 ”실크로드”라는 교역로가 있었다. 실크로드는 N + 1 개의 도시가 있고, 서쪽부터 도시 0, 도시 1, …, 도시 N이다. 도시 i - 1과 도시 i (1 ≦ i ≦ N) 사이의 거리는 Di이다. 무역상인 JOI 군은 도시 0에서 출발하여 도시를 차례로 경유하여 도시 N까지 실크로드를 수행하게 되었다. 도시 0에서 도시 N까지 M 이내에 이동해야한다. JOI 군은 각각의 날에 다음 두 가지 중 하나를 선택한다.

이동 : 현재의 도시에서 동쪽의 도시로 1 일 걸쳐 이동한다. 현재 도시 i - 1 (1 ≦ i ≦ N)에 있다면, 도시 i로 이동한다. 대기 : 이동하지 않고 현재 도시에서 1 일 대기한다.

그러나, 이동 할 때마다 피로도가 쌓여 간다. 실크로드에서는 매일 날씨변화가 나쁜 정도에 따라 이동에 어려움이 측정된다. JOI 군은 M 일 중 j 일째 (1 ≦ j ≦ M)의 날씨가 Cj임을 알고있다. 도시 i - 1에서 도시 i (1 ≦ i ≦ N)에 j 일째 (1 ≦ j ≦ M)로 이동하는 경우, 피로도가 Di × Cj 만 쌓여 버린다. 이동하지 않고 기다리는 날은 피로도가 쌓이지 않는다. JOI 군은 각각의 날에 행동을 잘 선택하여 가능한 피로도를 적게해서 이동하고 싶다. JOI 군이 M 이내에 도시 N으로 이동할 때의 피로도 총합의 최소를 구해라.

입력

입력은 1 + N + M 행으로 구성된다. 첫 번째 줄에는 두 개의 정수 N, M (1 ≦ N ≦ M ≦ 1000)가 공백을 구분으로 쓰여져있다.  이것은 실크로드가 N + 1 개의 도시로 구성되며, JOI 군이 실크를 도시 0에서 도시 N까지 M 이내에 실시해야한다는 것을 나타낸다. 다음 N 라인 중 i 번째 줄 (1 ≦ i ≦ N)에는 정수 Di (1 ≦ Di ≦ 1000)가 적혀있다. 이것은 도시 i - 1과 도시 i 사이의 거리가 Di임을 나타낸다. 다음 M 라인 중 j 번째 줄 (1 ≦ j ≦ M)에는 정수 Cj (1 ≦ Cj ≦ 1000)가 적혀있다. 이것은 j 일째 날씨 나쁨정도가 Cj임을 나타낸다.

출력

JOI 군이 M 이내에 도시 N으로 이동할 때의 피로도 총합의 최소를 한 줄로 출력한다.

예제

예제 1

입력

3 5
10
25
15
50
30
15
40
30

출력

1125

예제 2

입력

2 6
99
20
490
612
515
131
931
1000

출력

31589

My Sol

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
D = [0]+[int(input()) for _ in range(N)]
T = [0]+[int(input()) for _ in range(M)]
memo = [[0]*(N+1) for _ in range(M+1)]
for k in range(1, N+1):
    memo[k][k] = memo[k-1][k-1] + T[k]*D[k]

for j in range(1, N+1):
    for i in range(j+1, M+1):
        memo[i][j] = min(memo[i-1][j-1]+D[j]*T[i], memo[i-1][j])

print(memo[M][N])

얼마전에 처음 익혔던 배낭문제의 확장판이었다. 어느 날에 한 번 나아가게 된다면 이전 피로도 합에 현재 피로도를 더한 값이 있을 것이고, 이미 이전에 한참 달려 오늘 나아가지 않더라도 현재에 도달하는 경우 중 피로도 합이 더 적은 경우를 현재 피로도로 지정하는 것이다. 처음에 memo 배열의 기본값은 첫날부터 계속 달리는 것으로 간주하고, 행은 나아갈 수 있는 날들, 열은 나아가야 할 날들로 지정하였다. 그리고 행이 진행될 때마다 선택을 하는 것이다. 나아갈 것인지 말 것인지.

그래서 최솟값들을 각 좌표에 저장하고, memo[M][N]에 저장된 값을 출력하면 되겠다.

결과

맞았습니다!!