[백준][Java] 1149번 : rgb 거리

[문제 링크]

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

문제 설명

1 ~ N 번의 집을 아래 규칙을 따라서 빨강, 초록, 파랑 중 하나를 골라 색을 칠하는 데 드는 비용의 최솟값을 구한다.
1. 1번 집의 색 != 2번 집의 색
2. N번 집의 색 != N-1번 집의 색
3. i번 집의 색 != i-1번, i번 집의 색 != i-2번 집의 색

 

 

 

 

문제 풀이

다이나믹 프로그래밍으로 풀이

N번째 집의 색이 빨간색이라면,

• N+1번째 집의 색깔은 초록색 or 파란색
• N-1번째 집의 색깔은 초록색 or 파란색

dp 테이블은 2차원 배열로, column은 순서대로 빨간색(0), 초록색(1) , 파란색(2)이다.

dp[i][j]는 i번째 집을 j 색으로 칠했을 때, 0~i번 집을 칠하는 데 드는 비용의 최솟값을 의미한다.

 

점화식을 세워보면,

N번째 집이  빨간색일 경우

→ dp[N][0] = dp[N][0] + min(dp[N-1][1], dp[N-1][2])

 

N번째 집이 초록색일 경우

→ dp[N][1] = dp[N][1] + min(dp[N-1][0], dp[N-1][2])

 

N번째 집이 파란색일 경우

→ dp[N][2] = dp[N][2] + min(dp[N-1][0], dp[N-1][1])

 

전체코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

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

        int[][] dp = new int[n][3];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 3; j++) {
                dp[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < 3; j++) {
                if (j == 0) {
                    dp[i][j] = dp[i][j] + Math.min(dp[i - 1][1], dp[i - 1][2]);
                } else if (j == 1) {
                    dp[i][j] = dp[i][j] + Math.min(dp[i - 1][0], dp[i - 1][2]);
                } else if (j == 2) {
                    dp[i][j] = dp[i][j] + Math.min(dp[i - 1][0], dp[i - 1][1]);
                }
            }
        }
        int minCost = Math.min(dp[n - 1][0], Math.min(dp[n - 1][1], dp[n - 1][2]));
        System.out.println(minCost);
    }
}