[백준1149] RGB 거리 /Java

문제주소 :www.acmicpc.net/problem/1149

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보다 작거나 같은 자연수이다.

출력

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

예제 입력 1 복사

3
26 40 83
49 60 57
13 89 99

예제 출력 1 복사

96

 

<풀이법>

▒ 한줄 개념: 동적 계획법 ▒ 

동적 계획법(DP: Dynamic Programming)의 기초 문제 중 하나입니다.

동적 계획법의 핵심은 "DP 배열을 먼저 체크하고, 없을 경우 연산한다" 입니다.

이 문제 또한 DP 배열이 2차원으로 형성이 된다는 것을 제외하면, 다른 DP 기초 문제들과 같습니다.

 

▶최종적인 목표는 n번째 집까지 칠하는 것에 대한 최솟값입니다.

▶각 집은 3가지 색깔을 칠할 수 있습니다. 그 중 최솟값을 구해야 하므로, n번째 집을 각 색깔로 칠할 때의 값들 중 최솟값이 정답이 될 것입니다.

 

Top-Down 방식으로 이 문제를 풀어냈는데, 개념은 다음과 같습니다.

 

n번째 집을 빨간색으로 칠한다고 가정했을 때, n-1번째 집의 선택지는 초록, 파랑 입니다. 따라서 n번째 집을 빨간색으로 칠할 경우의 최소 비용은,

Min(n-1 번째 집을 초록색으로 칠하는 경우의 최소 비용, n-1번째 집을 파란색으로 칠하는 경우의 최소 비용) + n번째 집을 빨간색으로 칠하는 경우의 최소비용이 됩니다.

 

N번째 집을 특정 색깔로 칠할 경우의 최소값 구하는 방법

따라서 이것을 식으로 표현하면,

dp[N][green] = Min(dp[N-1][red], dp[N-1][blue]) + price[N][green] 

으로 나타낼 수 있습니다.

 

위 식을 이용하여 재귀함수에서 모든 N에 대한 최소값을 구해 dp 배열을 채우고, 최종적인 결과를 얻어낼 것입니다.

여기서 dp 배열을 채우는 이유는, 해당 연산 결과를 다음에 다시 이용하기 위해서이기 때문에, 위 식을 사용하기 전 조건문을 통해 이미 해당 값이 연산되어 저장되어 있는지 먼저 확인을 해주면 됩니다.

 

이와 같은 방식으로 재귀 함수를 이용하여 풀어내면 되는 문제가 되겠습니다.

 

<코드(Java)>

package Baekjoon;

import java.util.Scanner;

public class RGB_Distance_1149 {
    static int[][] prices;
    static int[][] dp;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int house_count = sc.nextInt();
        prices = new int[house_count][3];
        dp = new int[house_count][3];
        for(int i = 0 ; i < house_count; i++){
            for(int j = 0; j < 3 ; j++){
                prices[i][j] = sc.nextInt();
                dp[i][j] = 0;
            }
        }
        for(int i = 0; i < 3; i++){
            dp[0][i] = prices[0][i];
        }
        int min = Min(coloring(house_count-1, 0),coloring(house_count-1, 1));
        min = Min(min,coloring(house_count-1, 2));
        System.out.println(min);
    }

    static int coloring(int n, int i){
        if (dp[n][i] == 0){
            if(i == 0)
                dp[n][i] = Min(coloring(n - 1,1), coloring(n - 1,2)) + prices[n][0];
            else if(i == 1)
                dp[n][i] = Min(coloring(n - 1,0), coloring(n - 1,2)) + prices[n][1];
            else
                dp[n][i] = Min(coloring(n - 1,0), coloring(n - 1,1)) + prices[n][2];

        }
        return dp[n][i];
    }

    static int Min(int a, int b){return a > b ? b : a;}
}

 

 

더 많은 코드 보기(GitHub) : github.com/dwkim-97/CodingTest