[골드 5] 백준 10710 - 실크로드 (파이썬)

https://www.acmicpc.net/problem/10710

풀이

• N개의 도시간 거리: D[1] ~ D[N]
• M일간 날씨 나쁨 정도: C[1] ~ C[M]
• 도시 0 → 도시 N까지 정확히 N번 이동해야 함 (각 이동은 하루 소요)
• 한 날에 이동하거나, 대기 가능
• 이동일을 적절히 골라, 총 피로도 = D[i] * C[j]의 합이 최소가 되도록 해야 함

이 문제는 배낭 문제의 변형 + 구간 DP 또는 최적 부분 구조를 활용한 다이나믹 프로그래밍 문제이다.

먼저 dp[i][j]는 i일째까지 고려했을 때, j개의 도시를 이동한 최소 피로도를 나타낸다.

dp = [[1e9] * (N + 1) for _ in range(M + 1)]
dp[0][0] = 0

예를들어서 dp[3][1] = 3 이라면 3일 동안 도시 한칸만 이동했을때의 최소 피로도를 나타낸다.

for i in range(1, M + 1):         # i일차
    for j in range(0, N + 1):     # j번 이동한 경우
        # 대기할 경우
        dp[i][j] = dp[i - 1][j]
        # 이동할 경우 (j > 0 필요)
        if j > 0:
            dp[i][j] = min(
                dp[i][j],
                dp[i - 1][j - 1] + C[i - 1] * D[j - 1]
            )

dp[i][j] = dp[i - 1][j] → i일에 대기한 경우를 나타낸다.

dp[i][j] = dp[i - 1][j - 1] + C[i - 1] * D[j - 1] → i일에 j번째 도시로 이동한 경우를 나타낸다.

시간 복잡도 분석

O(N * M) = O(1000 * 1000) → 백만 이하

코드

# 백준 10710 - 실크로드
# 분류 : 다이나믹 프로그래밍

N, M = map(int, input().split())
D = [int(input()) for _ in range(N)]
C = [int(input()) for _ in range(M)]

dp = [[1e9] * (N + 1) for _ in range(M + 1)]
dp[0][0] = 0

for i in range(1, M + 1) :
    for j in range(0, N + 1) :
        dp[i][j] = dp[i - 1][j]

        if j > 0 :
            dp[i][j] = min(
                dp[i][j],
                dp[i - 1][j - 1] + C[i - 1] * D[j - 1]
            )

print(dp[M][N])