[백준 | Java] 1149 RGB거리

내 풀이

일정한 규칙을 가지고 연쇄적으로 연산이 진행되는 형태라서 다이나믹 프로그래밍으로 풀었다.

두 번째 집 부터 n번째 집까지의 최소 비용을 계산해 저장하며 연산을 진행해, 마지막인 n번째 집에서 각 색깔 중 최솟값을 찾아 반환한다.

풀이과정은 다음과 같다.

1. 두 번째 집부터 n번째 집까지 세 가지의 색깔 중, 더 작은 비용의 색깔을 각각 더하며 진행
   a. 두 번째 집의 빨간색에 첫 번째 집의 초록, 파랑색 중 더 작은 색의 비용을 더해서 저장
   b. 두 번째 집의 초록색에 첫 번째 집의 빨강, 파랑색 중 더 작은 색의 비용을 더해서 저장
   c. 두 번째 집의 파랑색에 첫 번째 집의 빨강, 초록색 중 더 작은 색의 비용을 더해서 저장
   d. 위의 과정 반복

   예제 5번 진행 예시
   

2. 마지막 집에서 세 가지의 색깔까지의 비용을 비교해 최솟값 반환

위의 1번 과정을 지난 예제 5번의 결과는 다음과 같다.

71 39 44 
71 127 94 
145 108 134 
197 163 208 
246 255 174 
239 187 261 
234 264 216 
276 282 253 

=> 가장 마지막 집인 276 282 253 중 최솟값은 253

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[][] homes = new int[n][3];

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 3; j++) {
                homes[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // 두 번째 집부터 n번째 집까지의 최소 비용 계산
        for (int i = 1; i < n; i++) {
            homes[i][0] += Math.min(homes[i - 1][1], homes[i - 1][2]);
            homes[i][1] += Math.min(homes[i - 1][0], homes[i - 1][2]);
            homes[i][2] += Math.min(homes[i - 1][0], homes[i - 1][1]);
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 3; j++) {
                System.out.print(homes[i][j] + " ");
            }
            System.out.println();
        }
        // 마지막 집의 최소 비용 중 최솟값 찾기
        int result = Math.min(homes[n - 1][0], Math.min(homes[n - 1][1], homes[n - 1][2]));
        System.out.println(result);
    }
}