백준 문제 풀이(1149번) java

문제

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

풀이

1번 집의 색은 2번 집의 색과 같지 않아야 한다.
N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다

처음에는 그리디 알고리즘으로 문제를 풀어보았지만 오답이었다. 매순간 가장 최선의 선택을 하는 것으로는 최솟값을 구할 수 없다.

위의 그림은 그리디 알고리즘으로 풀이하는 방법이고 아래 그림은 동적계획법으로 풀이하는 방법이다.(위의 그립처럼 풀면 최솟값을 구할 수 없음)

Cost와 Dp 2차원 배열을 선언한다. Dp는 누적 최솟값을 구하기 위해서 사용, Cost는 입력값을 받기 위해서 사용한다. Cost배열로 집의 수만큼의 RGB값(N*3)을 받고 Cost[0][0],Cost[0][1], Cost[0][2])를 Dp[0][0], Dp[0][1],Dp[0][2]에 넣어 Dp의 초기값을 설정해준 후에 Dp[N][Red],Dp[N][Green],Dp[N][Blue] 중 가장 작은 값을 구하면 된다. 가장 작은 값을 구하는 과정은

Dp[N][Red] = Math.Min(Dp[N-1][Green], Dp[N-1][Blue]) + Dp[N][Red]
Dp[N][Green] = Math.Min(Dp[N-1][Red], Dp[N-1][Blue]) + Dp[N][Green]
Dp[N][Red] = Math.Min(Dp[N-1][Red], Dp[N-1][Green]) + Dp[N][Blue]

다음과 같이 재귀함수를 구성하여 이 문제를 해결할 수 있다.

코드

package Category;

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

public class q_1149 {

    static final int Red = 0;
    static final int Green = 1;
    static final int Blue = 2;
    static int[][] Cost;
    static int[][] Dp;


    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        Cost = new int[T][3];
        Dp = new int[T][3];


        for (int i = 0; i < T; i++) {

            StringTokenizer st = new StringTokenizer(br.readLine(), " ");

            Cost[i][Red] = Integer.parseInt(st.nextToken());
            Cost[i][Green] = Integer.parseInt(st.nextToken());
            Cost[i][Blue] = Integer.parseInt(st.nextToken());
        }
		// Dp 2차원 배열 초기값 설정
        Dp[0][Red] = Cost[0][Red];
        Dp[0][Green] = Cost[0][Green];
        Dp[0][Blue] = Cost[0][Blue];

        System.out.println(Math.min(costMin(T - 1, Red), Math.min(costMin(T - 1, Green), costMin(T - 1, Blue))));
    }


    static int costMin(int N, int color) {

        if (Dp[N][color] == 0) {

            if (color == Red) {
                Dp[N][Red] = Math.min(costMin(N - 1, Green), costMin(N - 1, Blue)) + Cost[N][Red];
            } else if (color == Green) {
                Dp[N][Green] = Math.min(costMin(N - 1, Red), costMin(N - 1, Blue)) + Cost[N][Green];
            } else {
                Dp[N][Blue] = Math.min(costMin(N - 1, Red), costMin(N - 1, Green)) + Cost[N][Blue];
            }
        }
        return Dp[N][color];
    }
}