백준 실크로드 파이썬

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일 동안 도시 한칸만 이동했..