[알고리즘 PS(DP)] 1149번 RGB거리 자바 문제 풀이

문제

입출력 예제

---

접근 방법

조건

문제의 조건을 봐보자.

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

결국 이 말은 집의 색이 중복이 되면 안된다는 뜻이다. 그럼 집의 색이 중복이 되지 않게 놓기 위해서는 어떻게 놓아햐 할까?가 이 문제에 핵심중 하나이다.

최종 목적

우리는 이제 조건에 대해서 알았으니까 정답으로 가기위한 비용에 대해서 알아보자.

각 집에는 페인트의 가격이 있고, 해당 가격의 최소가 되는 색만 칠해서 최솟값을 출력하는것이 이 문제의 최종 목적이다.

이제 DP의 특성인 현재의 결과가 다음 결과에 영향을 미치는 구조에 대해서 알아보자.

DP 부분 해 찾기

집이 하나 일 때 :: N = 1

만약 집이 하나라고 했을 때를 생각해보자.

26 (최소)

40

83

그럼 당연히 가장 최소인 값을 선택하면 끝이다.

집이 둘 일 때 :: N = 2

26	40	83
49	60 (후보)	57 (후보)

이제 집이 둘이면 조금 생각을 해봐야 한다.

 

집이 둘이라면 그 전 결과(집이 하나일 때)에서 조건에 만족하는 집들(2번, 3번)중 최솟 값을 찾으면 되지 않을까?

 

그럼 Math.min(color[1], color[2]) 이렇게 나타날 것이다.

 

역시 집이 증가해서 i번째 까지 간다고 해도 마찬가지일 것이다.

 

이제 부분 해를 찾았으므로 코드로 표현해보자.

코드로 표현하기

위의 표를 코드로 변환하려면 이차원 배열이 필요하다.

그리고 입력된 값 배열과 i번째의 부분 해의 배열을 따로 나누기 위해서 두 개의 배열을 생성한다.

package algorithm.class11_dynamic_programming;

import java.io.*;

public class Prob03_RGB {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        int[][] arr = new int[n+1][3]; // 입력 배열
        int[][] dp = new int[n+1][3]; // 계산 결과 배열

        for (int i = 1; i < n + 1; i++) {
            String input = br.readLine();
            String[] str = input.split(" ");
            for (int j = 0; j < 3; j++) {
                arr[i][j] = Integer.parseInt(str[j]);
            }
        }

        dp[0][0] = dp[0][1] = dp[0][2] = arr[0][0] = arr[0][1] = arr[0][2] = 0;

        for (int i = 1; i < n + 1; i++) {
            dp[i][0] = Math.min(dp[i-1][1], dp[i-1][2]) + arr[i][0]; // red 일 때 : green과 blue중 최소 비용에 현재 red 비용을 더한다.
            dp[i][1] = Math.min(dp[i-1][0], dp[i-1][2]) + arr[i][1]; // green 일 떄 : red와 blue중 최소 비용
            dp[i][2] = Math.min(dp[i-1][0], dp[i-1][1]) + arr[i][2]; // blue 일 때 : red와 green의 최소 비용
        }

        bw.write(Math.min(Math.min(dp[n][0], dp[n][1]), dp[n][2])+""); // 부분 해의 결과 RGB중 최소 값을 출력한다.

        bw.flush();
        bw.close();
    }
}