[BOJ] 1149: RGB 거리 (JAVA)

문제

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

 

여담

예전에 풀었을 때는 풀이를 참고해서 풀었는데 이번에는 스스로 풀었다..! 실력이 크게 는 것 같지는 않지만 그래도 좀 뿌듯 ㅎㅎ

 

근데 DP 문제라는 것을 알고 있어서 쉽게 풀었지, 몰랐다면 헤맸을 것 같다. 각 유형을 공부한 뒤에 랜덤으로 문제를 푸는 연습도 꼭 해야 되겠다..!

 

풀이

모든 집을 칠하는 최소 비용을 구하기 위해 1번 집부터 N번 집을 칠하는 최소 비용을 누적하여 테이블을 채워 나가면 된다. 이때, 연속된 집은 같은 색으로 칠하지 못한다.

 

따라서 색칠하는 경우의 수는 다음과 같다.

• 현재 집에 빨간색을 칠하는 경우
  • 이전 집은 초록색 또는 파란색이 칠해져 있어야 함
  • dp[i][0] = Math.max(dp[i][1], dp[i][2])
• 현재 집에 초록색을 칠하는 경우
  • 이전 집은 빨간색 또는 파란색이 칠해져 있어야 함
  • dp[i][1] = Math.max(dp[i][0], dp[i][2])
• 현재 집에 파란색을 칠하는 경우
  • 이전 집은 빨간색 또는 초록색이 칠해져 있어야 함
  • dp[i][2] = Math.max(dp[i][0], dp[i][1])

 

예시

arr 배열

 

dp 배열

 

코드

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[][] arr = new int[n][3];
        int[][] dp = new int[n][3];
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < 3; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
                dp[i][j] = arr[i][j];
            }
        }

        for (int i = 1; i < n; i++) {
            // 현재 집에 빨강을 칠하는 경우, 이전 집은 초록이나 파랑만 가능
            dp[i][0] += Math.min(dp[i - 1][1], dp[i - 1][2]);
            // 현재 집에 초록을 칠하는 경우, 이전 집은 빨강이나 파랑만 가능
            dp[i][1] += Math.min(dp[i - 1][0], dp[i - 1][2]);
            // 현재 집에 파랑을 칠하는 경우, 이전 집은 빨강이나 초록만 가능
            dp[i][2] += Math.min(dp[i - 1][0], dp[i - 1][1]);
        }

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

---