DP. RGB 거리

문제

각 집마다 빨강, 초록, 파랑 중 하나를 택해서 칠하는 비용이 제시된다.
그 중에서 가장 적은 비용을 나오게 해야한다.

접근법

경우의 수를 생각하면 너무 많이 (2^N-1) 나오게 되는데, 이문제는 경우의 수를 생각하기보단, 위에서 부터 작은것을 뽑아 자신과 더해주는 경우로 생각하는것이 더 쉽다.

코드

package dp;

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

import static java.lang.Math.*;

public class RGBStreet {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());

        int[][] price = new int[N + 1][3];

        // 입력
        for (int i = 1; i <= N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            price[i][0] = Integer.parseInt(st.nextToken()); // Red
            price[i][1] = Integer.parseInt(st.nextToken()); // Green
            price[i][2] = Integer.parseInt(st.nextToken()); // Blue
        }

        int[][] dp = new int[N + 1][3];

        for (int i = 1; i <= N; i++) {
            dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + price[i][0];
            dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + price[i][1];
            dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + price[i][2];
        }

        int result = min(min(dp[N][0], dp[N][1]), dp[N][2]);

        bw.write(String.valueOf(result));

        bw.flush();
        br.close();
        bw.close();
    }
}

깨달음

dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + price[i][0]
오히려 자신을 유지하고 위에서 최소값을 뽑아 더하면 어렵지않다.