[Silver 1] [Java] RGB 거리 (1149번)

<RGB 거리>

문제 설명

RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑중에 하나로 칠하려고 한다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 이웃은 집 i-1과 집 i+1이고, 첫 집과 마지막 집은 이웃이 아니다.

각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 드는 비용이 주어질 때, 모든 집을 칠하는 비용의 최솟값을 구하는 프로그램을 작성하시오.

 

제한 사항

입력

첫째 줄에 집의 수 N이 주어진다. N은 1,000보다 작거나 같다. 둘째 줄부터 N개의 줄에 각 집을 빨강으로, 초록으로, 파랑으로 칠하는 비용이 주어진다. 비용은 1,000보다 작거나 같은 자연수이다.

출력

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

내 생각

개인적으로 어렵게 느꼈으며 좋은 문제라고 생각했습니다.

0	0	0
26	40	83
49	60	57
13	89	99

house 2차원 배열에 들어갈 수 입니다. (입력받을 숫자)

 

0	0	0
26	40	83
89	86	83
96	172	185

dp 2차원 배열에 들어갈 수입니다.

 

이 문제는 밑에 알고리즘을 통해 dp배열에 어떻게 값을 저장시킬지 생각해야 했습니다.

for (int i = 1; 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][0], dp[i-1][1]) + house[i][2];
}

 

작성 코드

import java.util.*;
 
public class Exam1149 {
 
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int answer = 0;
        int n = scan.nextInt();
        int[][] dp = new int[n+1][3];
        int[][] house = new int[n+1][3];
        
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < 3; j++) {
                house[i][j] = scan.nextInt();
            }
        }
        
        dp[0][0] = house[0][0];
        dp[0][1] = house[0][1];
        dp[0][2] = house[0][2];
        
        for (int i = 1; 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][0], dp[i-1][1]) + house[i][2];
        }
        
        answer = Math.min(Math.min(dp[n][0], dp[n][1]), dp[n][2]);
        System.out.println(answer);
    }
    
}

 

실행 결과