[c++] 백준 10710 실크로드

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

10710번: 실크로드

dp[i][j] : i번째 도시에 있을 때 날짜 j 라고 dp테이블을 정의하자.

날짜가 변함에 따라 할 수 있는 행동이 두 가지다.

1. 가만히 있는다.

2. 다음 도시로 간다.

단순한 dp문제라 간단히 해결할 수 있었다.

#include<bits/stdc++.h>
using namespace std;
#define INF 987654321
int n,m;
int dist[1111];
int weather[1111];
int dp[1111][1111];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m;
    for(int i=0; i<n; i++)
        cin>>dist[i];
    for(int i=0; i<m; i++)
        cin>>weather[i];
    for(int i=0; i<=1110; i++)
        for(int j=0; j<=1110; j++)
            dp[i][j] = INF;
    //dp[d][l] : 위치(l)에서 날짜(d)
    dp[0][0] = 0;
    for(int d=0; d<=m; d++){
        for(int l=0; l<=d && l<=n; l++){
            // 가만히 있는다.
            dp[d+1][l] = min(dp[d][l], dp[d+1][l]);
            // 다음 도시로 간다.
            dp[d+1][l+1] = min(dp[d+1][l+1], dp[d][l] + weather[d]*dist[l]);
        }
    }
    cout << dp[m][n];
    return 0;
}