[JAVA] 1149 RGB거리

풀이과정

이렇게 각 집마다 색깔을 겹치지 않게 색칠해줘야 한다.

그렇다면 2,2를 파랑으로 색칠할때 이미 최소값 계산이 다 되었다고 가정한 주황색중에 작은 값을 고른다.

(색이 겹치면 안되기 때문에 [1][2]는 제외시켰다.) 

주황색중 작은 값을 파랑에 더하면  최소값이 나온다.

그렇다면 이걸 sudo코드로 바꾸자면 [2][2] += min([1][0], [1][1])이다.

맨 초반 고정값은 그대로 넣어주고 그 값을 토대로 각 배열의 최소값들을 식으로 표현한다면 사진과 같이 나온다.

맨 아래 나온 N번째 식을 점화식을 토대로 최소값을 구해준다.

코드

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

public class backJoon1149 {
    static int[][] house;
    static int[][] dp;

    final static int Red = 0;
    final static int Green = 1;
    final static int Blue = 2;

    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());
        house = new int[N][3];
        dp = new int[N][3];
        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine());
            house[i][Red] =  Integer.parseInt(st.nextToken());
            house[i][Green] =  Integer.parseInt(st.nextToken());
            house[i][Blue] =  Integer.parseInt(st.nextToken());
        }
        dp[0][Red] = house[0][Red];
        dp[0][Green] = house[0][Green];
        dp[0][Blue] = house[0][Blue];

        System.out.println(Math.min(minCost(N-1, Red), Math.min(minCost(N-1, Green), minCost(N-1, Blue))));
    }
    public static int minCost(int N, int color) {
        //아직 방문하지 않은 집 확인
        if(dp[N][color] == 0) {
            //저장한 값을 불러와 최소값 저장
            if(color == Red) {
                dp[N][Red] = Math.min(minCost(N-1, Green), minCost(N-1, Blue)) + house[N][Red];
            }
            else if(color == Green) {
                dp[N][Green] = Math.min(minCost(N-1, Red), minCost(N-1, Blue)) + house[N][Green];
            }
            else {
                dp[N][Blue] = Math.min(minCost(N-1, Red), minCost(N-1, Green)) + house[N][Blue];
            }
        }
        return dp[N][color];
    }
}

결과

dp에 저장된 최소값들도 출력해줬다. 이렇게 보면 더 이해하기 편할것이다.