백준 (BOJ) 10710 실크로드 java dp

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

10710번: 실크로드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int[] distance = new int[n+1];
        for(int i=0; i<n; ++i){
            distance[i] = Integer.parseInt(br.readLine());
        }

        int[] weather = new int[m];
        for(int i=0; i<m; ++i){
            weather[i] = Integer.parseInt(br.readLine());
        }

        int[][] dp = new int[n][m];
        // 1.
        for(int i=0; i<n; ++i){
            for(int j=0; j<m; ++j){
                dp[i][j] = 987654321;
            }
        }

        // 2.
        for(int i=0; i<m; ++i){
            // 0번째 도시를 i일날 지나간다.
            dp[0][i] = distance[0] * weather[i];
        }

        // 3-1.
        for(int i=1; i<n; ++i){
            // 3-2.
            for(int j=1; j<m; ++j){
                for(int k=0; k<j; ++k){
                    dp[i][j] = Math.min(dp[i-1][k] + weather[j] * distance[i], dp[i][j]);
                }
            }
        }

        // 3-3.
        int ans = 987654322;
        for(int i=n-1; i<m; ++i){
            ans = Math.min(dp[n-1][i], ans);
        }

        System.out.print(ans);
    }
}

 

1. 모든 dp 배열의 값을 대략적으로 매우 큰 수 987654321로 초기화해준다. 그래야 최솟값으로 계속 갱신해나갈 수 있다.

 

2. 0번째 도시를 지나갈 때에 대한 초항 값을 dp 배열에 미리 초기화해준다.

 

3. 뛟

   3-1. 0번째는 지나왔다고 가정이 되어 있기 때문에 1번째 도시부터 진행한다.

   3-2. 1일날부터의 값을 구할 것이기 때문에 1일부터 시작한다. 

          그래야 누적을 하면서, 다른 말로 메모이제이션을 하면서 dp 배열을 진행시킬 수 있다.

          따지고 보면 이런 식이다. dp[1][1] = Math.min(dp[0][0] + weather[1] * distance[1], dp[1][1]);

          짙게 쓰여 있는 부분이 핵심이므로 해석해보면,

          0번째 도시를 0일날 지나왔을 때까지의 (최소) 누적 피로도 + 1번째를 1일날 지나갈 때 생길 피로도

 

   3-3. 모든 도시를 지나왔을 때 나오는 값들 중 가장 최소 골라내기. for문 내 초기값은 0부터 시작해도 된다.

          다만 m-1부터 시작한 이유는 결국 모든 도시를 다 지나와야하기 때문에,

          도시 갯수만큼의 최소 날짜가 지나갔기 때문이다.