[백준 17404: JAVA] RGB거리 2 / 동적 프로그래밍

개요

 

dp로 문제를 풀 수 있다.

이 문제는 dp를 생각하면 금방 풀이할 수 있지만, 약간의 조건이 추가되어 있기 때문에 생각을 좀 해야 했다.

첫 집과 마지막 집도 색이 같으면 안 된다는 조건이 있기 때문에

첫 집의 색을 고정 시키고 두 번째 집부터 마지막 집까지 3가지 색을 조합하며 최솟값을 구하여 dp배열을 채워준다.

그 후 마지막에 최솟값을 구할 때 고정시킨 첫 집의 색과 다른 마지막 집의 값들에서 최솟값을 추출해내면 된다.

 

문제

 

RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑 중에 하나로 칠하려고 한다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 이웃은 집 i-1과 집 i+1이고, 첫 집과 마지막 집도 이웃이다.

각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 드는 비용이 주어질 때, 모든 집을 칠하는 비용의 최솟값을 구하는 프로그램을 작성하시오.

 

입력

 

풀이

 

dp[][]을 선언한다.

모든 dp문제가 그렇듯이 나의 생각에는 dp문제를 풀 때는 dp배열을 1차원으로 선언할지, 2차원으로 선언할지....

와 dp의 행, 열, 값은 무엇을 의미하는지가 가장 중요하고 어렵다고 생각한다.

 

일단 이 문제에서 dp[i][j] = k가 있다면, 아래와 같은 의미를 가진다.

-> 1~i번째 집까지 칠하고 i번째 집은 j색으로 칠했을 때의 최소비용 = k를 의미한다.

 

따라서 j는 0~2로 표현가능하게 선언하고 각각을 R, G, B를 의미하게 한다.

 

개요에서 말했듯이 첫 집과 마지막 집 또한 이웃이기 때문에 

 

첫 집 : RED 인 경우 ▶ 첫 집의 GREEN, BLUE의 DP값을 무한대로 설정한다.

첫 집 : GREEN 인 경우 ▶ 첫 집의 RED, BLUE의 DP값을 무한대로 설정한다.

첫 집 : BLUE 인 경우 ▶ 첫 집의 RED, GREEN의 DP값을 무한대로 설정한다.

 

위와 같이 3가지 경우로 나눠서 계산한 뒤

 

첫 집 : RED 인 경우 ▶ 마지막 집을 GREEN, BLUE로 칠한 DP값 중에 최솟값을 구한다.

첫 집 : GREEN 인 경우 ▶ 마지막 집을 RED, BLUE로 칠한 DP값 중에 최솟값을 구한다.

첫 집 : BLUE 인 경우 ▶ 마지막 집을 RED, GREEN로 칠한 DP값 중에 최솟값을 구한다.

 

 

코드

 

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


public class Main {
    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    // 최대 비용 값
    private static final int INF = 1_000 * 1_000;
    static int n;
    // 각 칠하는 비용에 대한 정보
    static int arr[][];
    // 행은 몇번째 집인지를 의미하고 열은 0,1,2 각각은 R, G, B의 색을 칠했을 때를 의미한다.
    // i번째까지 칠하고 열의 색으로 칠했을 때의 최솟값을 저장하고 있다.
    static int dp[][];
    static int answer = INF;

    public static void main(String[] args) throws IOException {
        n = Integer.parseInt(br.readLine());
        arr = new int[n + 1][3];
        dp = new int[n + 1][3];

        // 입력 값 저장
        for(int i = 1 ; i <= n; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j = 0 ; j < 3; j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // k = 0 -> RED, 1 -> GREEN, 2 -> BLUE로 첫 집을 칠하는 경우이다.
        for(int k = 0; k < 3; k++) {
            //RED, GREEN, BLUE로 칠하는 경우 각 색을 제외한 나머지는 INF로 초기화 해준다.
            for(int i = 0 ; i < 3; i++) {
                if(i == k) dp[1][i] = arr[1][i];
                else dp[1][i] = INF;
            }

            // 열의 값인 0 -> RED, 1 -> GREEN, 2 -> BLUE로 칠했을 때의 최소값을 의미한다.
            for (int i = 2; i <= n; i++) {
                dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + arr[i][0];
                dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + arr[i][1];
                dp[i][2] = Math.min(dp[i - 1][0], dp[i - 1][1]) + arr[i][2];
            }

            // 정답인 최솟값을 구하는 부분
            for(int i = 0 ; i < 3; i++)
                if(i != k) answer = Math.min(answer, dp[n][i]);
        }


        bw.write(answer + "\n");

        bw.close();
        br.close();
    }
}