[S1] 백준 1149 RGB거리 - Java

https://www.acmicpc.net/problem/11720

11720번: 숫자의 합

동적 계획법을 활용하는 문제이다.

다른 동적 계획법 문제와 다르게 다소 까다로운 부분이 있었다.

양 옆으로 같은 색깔의 집이 오면 안된다는 규칙과, 집을 칠하는 비용의 최솟값을 구해야 했기 때문이다.

빨강, 초록, 파랑으로 시작하는 모든 경우의 수를 찾아나가야 했다.

 

[풀이]

import java.util.Scanner;

public class N_1149 {
    static int[][] cost;
    static int[][] dp;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 집의 수

        cost = new int[n][3];
        dp = new int[n][3]; // 누적 값을 저장할 dp 배열 생성

        // RGB 비용 입력받기
        for (int i = 0; i < n; i++) {
            cost[i][0] = sc.nextInt();
            cost[i][1] = sc.nextInt();
            cost[i][2] = sc.nextInt();
        }

        // dp 배열 초기값 지정
        dp[0][0] = cost[0][0];
        dp[0][1] = cost[0][1];
        dp[0][2] = cost[0][2];

        System.out.println(Math.min(rgbHouse(n-1, 0), Math.min(rgbHouse(n-1, 1), rgbHouse(n-1, 2))));
    }
    // Top-down 방법
    static int rgbHouse(int n, int color) {
        if (dp[n][color] == 0) {
            if (color == 0) { // 0일 때 1과 2를 찾음
                dp[n][0] = Math.min(rgbHouse(n-1, 1), rgbHouse(n-1, 2)) + cost[n][0];
            } else if (color == 1) { // 1일 때 0과 2를 찾음
                dp[n][1] = Math.min(rgbHouse(n-1, 0), rgbHouse(n-1, 2)) + cost[n][1];
            } else { // 2일 때 0과 1을 찾음
                dp[n][2] = Math.min(rgbHouse(n-1, 0), rgbHouse(n-1, 1)) + cost[n][2];
            }
        }
        return dp[n][color];
    }
}

Top-down 방법을 사용하였다. 이는 위에서 시작하여 아래로 흘러가는 방법이다.

그래서 main문에서 시작할 때 rgbHouse 함수의 첫 번째 인자를 n-1로 두었다. 그러면 dp[2] 부터 시작하여 초기값이 들어 있는 dp[0]까지 차례로 재귀 함수를 통하여 탐색할 것이다.

 

dp 배열 값이 차례로 채워지지 않았기 때문에 헷갈리는 부분이 있어서 직접 필기로 쓰면서 해당 코드를 이해해보았다.

백준에 있는 예시 입력으로 해보았다.

dp[0]은 [26, 40, 83]으로 미리 입력 받은 cost[0] 값으로 채워져 있는 상태이다.

우리는 dp[2][0], dp[2][1], dp[2][2]를 각각 계산하여 여기서 최소값을 찾아낼 것이다. 그 아래 인덱스와의 합을 계산해서 더 작은 값을 계산하여 dp 배열에 저장한다.

계산이 거듭될 수록 dp 배열에 저장되어 있는 값을 사용하는 빈도가 높아지기 때문에 좀 더 효율적으로 연산을 진행할 수 있다. 이것이 다이나믹 프로그래밍의 이점이다.

 

이번에는 다른 풀이를 참고하여 풀었다.

규칙을 지키면서, 가장 최솟값의 경로를 찾아내야 했기 때문에 어려운 부분이 있었다.

여러 문제를 풀면서 재귀에 조금씩 익숙해졌다 싶다가도 아직 응용하기에는 역부족이라는 생각이 든다.

좀 더 재귀에 익숙해지도록 문제를 많이 풀어봐야겠다.

 

[Reference]

https://st-lab.tistory.com/128

[백준] 1149번 : RGB거리 - JAVA[자바]