백준 1149번: RGB 거리[JAVA]

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

1149번: RGB거리

 

[정답 코드]

import java.io.*;
import java.util.*;

public class Main {
    static int[][] houses;
    static int[][] cost;
    static int N;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        N = Integer.parseInt(st.nextToken());
        houses = new int[N][3];
        cost = new int[N][3];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < 3; j++) {
                houses[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // 초기값 세팅
        cost[0][0] = houses[0][0];
        cost[0][1] = houses[0][1];
        cost[0][2] = houses[0][2];

        System.out.println(Math.min(Math.min(dp(N-1,0), dp(N-1,1)), dp(N-1,2)));
    }

    // 로직
    public static int dp(int N, int color) {
        if (cost[N][color] == 0) {
            if (color == 0) {
                return cost[N][color] = Math.min(dp(N-1, 1), dp(N-1, 2)) + houses[N][color];
            }
            if (color == 1) {
                return cost[N][color] = Math.min(dp(N-1, 0), dp(N-1, 2)) + houses[N][color];
            }
            if (color == 2) {
                return cost[N][color] = Math.min(dp(N-1, 0), dp(N-1, 1)) + houses[N][color];
            }
        }
        return cost[N][color];
    }
}

 

[설명]

저번 DP문제에서 설명했듯이 DP 문제는 3가지 방법을 따라야 한다.

1. 테이블 정의

2. 점화식 찾기

3. 초기값 정하기

 

1. 테이블 정의하기

dp[N] = N일째 집일 때 집을 칠하는 최소 비용

 

2. 점화식 찾기

cost [N][Red] = Math.min(dp[N-1][Green], dp[N-1][Blue]) + houses[N][Red]

cost [N][Green] = Math.min(dp[N-1][Red], dp[N-1][Blue]) + houses[N][Green]

cost [N][Blue] = Math.min(dp[N-1][Red], dp[N-1][Green]) + houses[N][Blue]

Math.min(Math.min(dp[N-1][Red], dp[N-1][Green]), dp[N-1][Blue])

 

3. 초기값 세팅

cost[0][0] = houses[0][0];
cost[0][1] = houses[0][1];
cost[0][2] = houses[0][2];

 

나머지는 코드와 같다.

나는 스스로 테이블정의, 점화식찾기, 초기값 세팅을 처음으로 스스로 구해냈다! 하지만 여기까지였다. 그 다음 코드로 구현하는 부분에서 막혀버려서 구글링을해 코드를 구현했다.