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

 

관련글

 

Dynamic Programming 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제 링크는 여기를 참조

 

 

이 문제는 N개의 집이 1열로 위치할 때, 인접한 집과 색이 같지 않도록 빨강, 초록, 파랑으로 칠하는 경우의 수 중 그 비용이 가장 작은 것을 구하는 문제이다.

 

 

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]

 

기저 상태는 N=0번째 집인 경우이다. 미리 arr[0], arr[1], arr[2]로 각각 설정한다.
기저 상태 : DP[0][0] = arr[0], DP[0][1] = arr[1], DP[0][2] = arr[2]

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

 

 

3. 코드

 

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

 

1) Bottom-up 방식

import java.io.*;

public class Main{
    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));
        
        dp = new int[1000][3];
        int N = Integer.parseInt(br.readLine());
        
        String line[] = br.readLine().split(" ");
        dp[0][0] = Integer.parseInt(line[0]);
        dp[0][1] = Integer.parseInt(line[1]);
        dp[0][2] = Integer.parseInt(line[2]);
        
        for(int i=1; i < N; i++){
            line = br.readLine().split(" ");
            int n1 = Integer.parseInt(line[0]);
            int n2 = Integer.parseInt(line[1]);
            int n3 = Integer.parseInt(line[2]);
            
            dp[i][0] = Math.min(dp[i-1][1], dp[i-1][2]) + n1;
            dp[i][1] = Math.min(dp[i-1][0], dp[i-1][2]) + n2;
            dp[i][2] = Math.min(dp[i-1][0], dp[i-1][1]) + n3;
        }
        
        int result = dp[N-1][0];
        for(int i=1; i < 3; i++){
            if(dp[N-1][i] < result){
                result = dp[N-1][i];
            }
        }
        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));
        
        dp = new int[1000][3];
        arr = new int[1000][3];
        int N = Integer.parseInt(br.readLine());
        
        for(int i=0; i < N; i++){
            String line[] = br.readLine().split(" ");
            arr[i][0] = Integer.parseInt(line[0]);
            arr[i][1] = Integer.parseInt(line[1]);
            arr[i][2] = Integer.parseInt(line[2]);
        }
        
        int result = Integer.MAX_VALUE;
        for(int i=0; i < 3; i++){
            int temp = topDown(N-1, i);
            result = Math.min(result, temp);
        }
        bw.write(String.valueOf(result));
        bw.flush();
        br.close();
    }
    
    // Top-down 방식
    public static int topDown(int n, int color){
        if(n == 0) return arr[n][color]; // 기저 상태는 n=0일 때.
        if(dp[n][color] > 0) return dp[n][color]; // 이미 값이 지정되었다면 바로 반환
        
        dp[n][color] = Math.min(topDown(n-1, (color+1) %3), topDown(n-1, (color+2)%3)) + arr[n][color];
        return dp[n][color];
    }
}

 

 

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