Backjoon(백준) 1149번 - RGB거리(Java)

1. 풀이 과정

i번째의 집을 빨강, 초록, 파랑으로 칠하는 각각의 최소 비용 케이스를 하나의 2차원 배열에 저장하여 최종 n번째 집의 최소 비용을 구한다 (i <= n)

 

* 풀이 과정 예시

 1) 첫 번째 집을 칠하는 빨강, 초록, 파랑의 각각 최소 비용은 각 색상의 색칠 비용 그 자체이다. 

 2) 두 번째 집을 칠하는 각 색상의 최소 비용은 첫 번째 집에서 계산된 각 색상의 최소 비용 값들을 이용하여 계산한다.

  예를들어, 두 번째 집에서 빨강색을 고른 경우의 최소 비용은 : 첫 번째집의 초록, 파랑색 비용중 작은 값을 두번 째 집의 빨강색 비용에 더한 값이 된다. =  min (첫 번째집 초록색 비용, 첫 번째집 파랑색 비용) + 두 번째 집 빨강색 비용. 같은 방식으로 두 번째 집에서 초록, 파랑을 고른 경우의 최소 비용을 계산하고 결과를 배열에 저장한다.

 3) 위 과정을 반복하여 n 번째 집을 칠하는 색상의 최소 비용을 도출한다.

 

2. 코드 구현

 - 각각의 집을 색상별로 구분하는 최솟값을 저장해야 하기 때문에 집을 저장하는 배열과 색상을 저장하는 배열이 있어야한다. 따라서 2차원 배열을 선언한다.

 

import java.util.Scanner;

public class RGBdistance {

    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        
        int[][] house = new int[1001][3]; // 각 집(i)의 빨강(0) 초록(1) 파랑(2) 비용을 2차원 배열에 저장.
        int[][] dp = new int[1001][3]; // 각 집을 칠할 때 색상별 최소비용을 dp 배열에 저장.
        int result = 0;
        int n = sc.nextInt();
        
        for (int i = 1; i <= n; i++) {
            house[i][0] = sc.nextInt();
            house[i][1] = sc.nextInt();
            house[i][2] = sc.nextInt();
        }
        
        dp[1][0] = house[1][0]; // 첫 집을 칠할 때 색상별 최소 비용은 각 집의 색상별 비용 그 자체임.
        dp[1][1] = house[1][1];
        dp[1][2] = house[1][2];
        
        for (int i = 2; i <= n; i++) {
            dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + house[i][0];
            dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + house[i][1];
            dp[i][2] = Math.min(dp[i - 1][1], dp[i - 1][0]) + house[i][2];
        }
        
        result = Math.min(dp[n][2], Math.min(dp[n][0], dp[n][1]));
        
        System.out.println(result);
        
        sc.close();
    }

}

 

문제 링크

( https://www.acmicpc.net/status?user_id=sdwe22&problem_id=1149&from_mine=1 )