백준 17404 - RGB거리 2 / Java

문제

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

17404번: RGB거리 2

기존 RGB거리 문제에서 첫집과 마지막집도 이웃이라는 조건이 추가된문제 따라서 원형구조를 이룬다.

첫집과 마지막집의 색깔이 달라야하므로 첫번째집의 색을 고정하고 답을구한뒤 3가지의 색깔중 가장 비용이 적은 것을 답으로 출력한다.

 

알고리즘

1. 첫번째 집의 색을 고정한다. 나머지 색깔의 배열에 나올수있는 비용의 최댓값+1을 넣어줘서 필요없게만든다.

2. 2차원배열을 사용하여 이웃끼리 색이 겹치지않게 색칠하는 비용을 구한다.

3. 비용의 최솟값을 출력한다.

소스코드

/*
 * BOJ17404
 * 2020.01.20
 * Hyeonseong
 */
import java.util.*;
public class BOJ17404
{
    public static void main(String[] args) 
    {
        Solution s = new Solution();
    }
}
class Solution{
    public Solution() {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[][] dp = new int[n+1][3];
        int[][] arr = new int[n+1][3];
        for(int i=1;i<n+1;i++) {
            for(int j=0;j<3;j++) {
                arr[i][j] = scan.nextInt();
            }
        }
        
        int answer = Integer.MAX_VALUE;
        for(int k=0;k<3;k++) {
            for(int j=0;j<3;j++) {
                if(j==k) {
                    dp[1][j] = arr[1][j];
                }
                else {
                    dp[1][j] = 1000*1000+1;
                }
            }
            for(int i=2;i<n+1;i++) {
                dp[i][0] = Math.min(dp[i-1][1],dp[i-1][2])+arr[i][0];
                dp[i][1] = Math.min(dp[i-1][0],dp[i-1][2])+arr[i][1];
                dp[i][2] = Math.min(dp[i-1][1],dp[i-1][0])+arr[i][2];
            }
            for(int i=0;i<3;i++) {
                if(i!=k) {
                    answer = Math.min(answer,dp[n][i]);
                }
            }
        }
        System.out.println(answer);        
    }
}