[백준 10710] 실크로드

문제

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

 

알고리즘

동적 계획법

 

풀이

날씨가 궂으면 쉬고, 좋으면 현재 도시에서 다음 도시로 가는 그리디한 해는 금방 반례가 나오게 됩니다. 현재 날씨가 좋지 않더라도 나중에 거리가 짧은 도시 사이를 좋은 날씨로 가게 되는 케이스가 있다면 걸리기 때문입니다. 즉 모든 상황을 고려할 수 있는 동적 계획법으로 해결하도록 합시다.

 

$cache[i][j]$= $i$날에 $j$ 도시에 위치할 때, 얻게 되는 최소 피로도

 

++

$cache$ 값을 갱신할 때, 우리가 필요로 하는 정보는 직전 날에 대한 정보뿐 입니다. 2일 전, 3일 전 정보가 필요가 없습니다. 슬라이딩 윈도우를 통하여 $cache[2][1000]$로 메모리를 최적화할 수 있습니다.

 

코드

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define REP(i,n) for(int i=1;i<=n;++i)
#define FAST cin.tie(NULL);cout.tie(NULL); ios::sync_with_stdio(false)
using namespace std;

int N, M;
int dist[1005];
int piro[1005];
int cache[1005][1005];
int main() {
    FAST;
    memset(cache, 0x3f, sizeof(cache));
    cin >> N >> M;
    REP(i, N) cin >> dist[i];
    REP(i, M) cin >> piro[i];
    cache[0][0] = 0;
    for (int i = 1;i <= M;++i) // 날
        for (int j = 0;j <= N;++j)  // 위치(도시)
            cache[i][j] = min(cache[i - 1][j], cache[i - 1][j - 1] + dist[j] * piro[i]);
    cout << cache[M][N];
    return 0;
}