(1149) RGB거리

문제

문제
RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.1번 집의 색은 2번 집의 색과 같지 않아야 한다.N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

입력
첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

출력
첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

---

문제 풀이

해당 문제는 DP 알고리즘으로 해결을 할 수 있는 문제이다. n * n 2차원 배열을 arr와 dp이름이 생성하고 기본적으로 입력되는 값을 arr에 입력을 하고 arr[0] 값을 dp[0] 값으로 초기화 해준다. 이러한 작업을 마치면 아래와 같은 모양이 된다. 

여기서 조건은 같은 col 값에 있는 값이 연속적으로 더해지면 안되는 조건이 있기 때문에 다음 dp배열 값에는 대각선으로 있는 값들만 더해야 한다. 그리고 더해지면서 기존에 더해져 있는 값을 비교해서 더 작은 값을 dp[i] 에 입력하여야 한다.

 

dp[1] 값을 채우면 아래와 같다.   

한번 dp[2] 값들을 채우면 아래와 같다.

여기서 마지막 배열의 값에서 제일 작은 값은 96 이므로 96을 반환한다.

---

나의 답안

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        int[][] cost = new int[n][3]; // RGB 색상 비용을 저장할 배열

        // 입력받은 색상 비용 저장
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 3; j++) {
                cost[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // 다이나믹 프로그래밍으로 최소 비용 계산
        int[][] dp = new int[n][3]; // 각 집을 해당 색으로 칠할 때까지의 최소 비용을 저장할 배열
        dp[0][0] = cost[0][0]; // 첫 번째 집을 빨간색으로 칠할 때 최소 비용
        dp[0][1] = cost[0][1]; // 첫 번째 집을 초록색으로 칠할 때 최소 비용
        dp[0][2] = cost[0][2]; // 첫 번째 집을 파란색으로 칠할 때 최소 비용

        for (int i = 1; i < n; i++) {
            // i번째 집을 빨간색으로 칠할 때의 최소 비용 계산
            dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + cost[i][0];
            // i번째 집을 초록색으로 칠할 때의 최소 비용 계산
            dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + cost[i][1];
            // i번째 집을 파란색으로 칠할 때의 최소 비용 계산
            dp[i][2] = Math.min(dp[i - 1][0], dp[i - 1][1]) + cost[i][2];
        }

        // n번째 집까지 칠하는데 드는 최소 비용 출력
        System.out.println(Math.min(dp[n - 1][0], Math.min(dp[n - 1][1], dp[n - 1][2])));
    }
}