알고리즘 풀이 - 백준 17404(RGB거리 2, DP)

 

관련글

 

Dynamic Programming 관련 포스팅은 여기를 참조
관련 문제인 1149(RGB  거리) 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

이 문제는 1~N번째 집이 놓여있을 때, 인접한 집이 색이 다르게 색칠하는 경우 가장 최소의 비용으로 칠할 때의 비용을 구하는 문제다.

주목할 점은 1번째와 N번째 또한 같은 색이어서는 안된다는 것이다.

 

 

2. 풀이

 

이 문제는 간단하게 DP로 해결이 가능하다.

인접한 위치의 집과 색상이 다르면 되기 때문에 이전 위치와 동일한 색상으로 칠하지 않는 색 중 가장 최소 비용인 것을 구해나가면 되기 때문이다.

이 문제에서 State는 N개의 집 중 몇 번째에 위치했느냐, 어떤 색으로 칠해졌느냐의 2가지이다. 색은 3개이므로, 0, 1, 2라고 표현하자. 그러면 State를 저장하는 배열은 DP[][]로 지정할 수 있다. 크기는 N * 3으로 하면 된다.(집의 수 N, 색의 수 3)

문제의 정의는 다음과 같다.
정의 : DP[N][i] = N번째의 집을 이전 / 다음 집과 색상이 겹치지 않는 최소 비용으로 칠한 비용

 

그러면, 각 N번째일 때, 0, 1, 2로 칠하는 경우를 다음과 같이 구할 수 있을 것이다. 각 위치의 집을 칠하는 배열을 arr 배열이라고 하자.

DP[N][0] = Math.min(DP[N-1][1], DP[N-1][2]) + arr[0]
DP[N][1] = Math.min(DP[N-1][0], DP[N-1][2]) + arr[1]
DP[N][2] = Math.min(DP[N-1][0], DP[N-1][1]) + arr[2]

 

 

그런데, 0번째와 N-1번째 또한 같은 색이어서는 안된다는 부분을 처리할 수 있어야 한다. 위와 같은 점화식을 단순히 이용하다가는 맨 앞과 뒤가 같은 색으로 칠해지는 경우가 정답이 되도록 처리될 수 있다.

이를 처리하기 위한 가장 효율적인 방법은 0번째 집의 색을 미리 정해놓고 해당 색으로 마지막 집을 칠할 시 절대 최소의 비용이 나올 수 없도록 설정하는 것이다.

 

문제에서는 집의 수가 최대 1,000개이며 칠하는 비용의 수는 최대 1,000으로 정해질 수 있다. 즉, 1,000 x 1,000 = 1백만이므로 특정 색으로 고정하였다면 다른 색으로 칠하는 경우를 1백만 보다 더 높은 수로 미리 지정해두면 된다!

이를 기저 상태를 처리하는 방식으로 수행하면 된다.

 

기저 상태는 N=0번째 집인 경우이다.
① 0번째 집을 0번 색상으로 칠하는 경우 : DP[0][0] = arr[0], DP[0][1] = 1000001, DP[0][2] = 1000001
② 0번째 집을 1번 색상으로 칠하는 경우 : DP[0][0] = 1000001, DP[0][1] = arr[1], DP[0][2] = 1000001
③ 0번째 집을 2번 색상으로 칠하는 경우 : DP[0][0] = 1000001, DP[0][1] = 1000001, DP[0][2] = arr[2]

점화식은 상단에 기재한 DP[N][i]를 구하는 경우의 수를 그대로 사용한다.

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

 

1) Bottom-up 방식

import java.io.*;

public class Main{
    static int[][] arr;
    static int[][] dp;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        arr = new int[1000][3];
        dp = new int[1000][3];
        int N = Integer.parseInt(br.readLine());
        
        // 우선 원래 배열 초기화
        for(int i=0; i < N; i++){
            String[] line = br.readLine().split(" ");
            for(int j=0; j < 3; j++){
                arr[i][j] = Integer.parseInt(line[j]);
            }
        }
        
        int result = Integer.MAX_VALUE;
        // 0번째 집을 어떤색으로 칠하느냐에 따라 각각 최소값을 구할 수 있으니 3번 반복
        for(int i=0; i < 3; i++){
        
            // 우선 0번째 집을 현재 i값과 같을 때 해당 집은 원 배열의 값으로
            // 나머지는 최소 비용이 나올 수 없는 값으로 초기화 한다.
            for(int j=0; j < 3; j++){
                if(i==j){
                    dp[0][j] = arr[0][i];
                } else {
                    dp[0][j] = 1000 * 1000 + 1;
                }
            }
            
            // 반복문을 통해 모든 집을 칠하는 경우를 구해나간다.
            for(int j=1; j < N; j++){
                dp[j][0] = Math.min(dp[j-1][1], dp[j-1][2]) + arr[j][0];
                dp[j][1] = Math.min(dp[j-1][0], dp[j-1][2]) + arr[j][1];
                dp[j][2] = Math.min(dp[j-1][0], dp[j-1][1]) + arr[j][2];
            }
            
            // n-1번째까지 구해진 값 중 최소 비용의 값을 구한다.
            for(int j=0; j < 3; j++){
                // 0번째와 N-1번째가 같은 경우는 애초에 Count하지 않는다.
                if(i == j) continue;
                result = Math.min(result, dp[N-1][j]);
            }
        }
        bw.write(String.valueOf(result));
        bw.flush();
        br.close();
    }
}

 

2) Top-Down 방식

import java.io.*;

public class Main{
    static int[][] dp;
    static int[][] arr;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        arr = new int[1000][3];
        int N = Integer.parseInt(br.readLine());
        
        for(int i=0; i < N; i++){
            String line[] = br.readLine().split(" ");
            for(int j=0; j < 3; j++){
                arr[i][j] = Integer.parseInt(line[j]);
            }
        }
        
        int result = Integer.MAX_VALUE;
        for(int i=0; i < 3; i++){
            // 매번 초기화를 해줘야 함. 그렇지 않으면 이전 값 그대로 사용
            dp = new int[1000][3];
            
            // topDown 으로 N-1번째의 각 경우의 수를 모두 구해야 하므로 반복문 추가
            for(int j=0; j < 3; j++){
                topDown(N-1, j, i);
            }
            
            for(int j=0; j < 3; j++){
                // 0과 N-1의 집을 같은 색으로 칠하는 경우는 계산하지 않음
                if(i == j) continue;
                result = Math.min(result, dp[N-1][j]);
            }
        }
        bw.write(String.valueOf(result));
        bw.flush();
        br.close();
    }
    
    // Top-down 방식
    // 배열의 길이, 현재 칠하는 color, 첫 번째 집의 fix된 값을 parameter로 전달
    public static int topDown(int n, int c, int fix){
        if(n == 0){
            // fix 값이면 원래의 값으로, 아니면 최소 비용이 나올 수 없는 값으로
            if(c == fix) dp[n][c] = arr[n][c];
            else dp[n][c] = 1000 * 1000 + 1;
            return dp[n][c];
        }
        if(dp[n][c] > 0) return dp[n][c]; // 이미 값이 지정되었다면 바로 반환
        
        dp[n][c] = Math.min(topDown(n-1, (c+1) %3, fix), topDown(n-1, (c+2)%3, fix)) + arr[n][c];
        return dp[n][c];
    }
}

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.