0x10 - DP : BOJ1149 RGB 거리

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));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st;
        int[] r = new int[1005];
        int[] g = new int[1005];
        int[] b = new int[1005];
        for (int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine()," ");
            r[i] = Integer.parseInt(st.nextToken());
            g[i] = Integer.parseInt(st.nextToken());
            b[i] = Integer.parseInt(st.nextToken());
        }

        // 1. 테이블 설정
        // d[i][3] : i번째 집이 각각 r / g / b일 때 합의 최솟값을 저장
        int[][] d = new int[1005][3];

        //2. 초기값 설정
        d[1][0] = r[1]; d[1][1] = g[1]; d[1][2] = b[1];

        // 3. 점화식
        for (int i = 2; i <= n; i++) {
            d[i][0] = Math.min(d[i-1][1], d[i-1][2]) + r[i];
            d[i][1] = Math.min(d[i-1][0], d[i-1][2]) + g[i];
            d[i][2] = Math.min(d[i-1][0], d[i-1][1]) + b[i];
        }
        System.out.println(Math.min(Math.min(d[n][0], d[n][1]), d[n][2]));
    }
}

1. 테이블설정 : d[i][3] : i번째 집이 각각 r / g / b일 때 합의 최솟값을 저장

• 즉 d[i][0] : i번째 집이 r인 경우 합의 최솟값
  , d[i][1] : g인경우, d[[i][2] : b인경우 최솟값, ...

2. 초기값 설정 :첫번째 집의 각 rgb 값을 넣어준다

3. 점화식
   [0] : i번째 집이 r인 경우 -> i-1번째 집의 g,b중 작은값 선택 + r[i]

[1] : i번째 집이 g인 경우 -> i-1번째 집의 r,b중 작은값 선택 + g[i]

[2] : i번째 집이 b인 경우 -> i-1번째 집의 r,g중 작은값 선택 + b[i]