1149.RGB거리

문제

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

• 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
• N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
• i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

## 입력

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

## 출력

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

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
0.5 초 (추가 시간 없음)	128 MB	105821	58495	43577	54.494%

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

풀이

알고리즘 흐름 + 코드 

첫번째 시도

package 기초1.Day19.정해영;  

import java.util.Scanner;  

public class RGB거리 {  

    public static void main(String[] args) {  

        Scanner sc = new Scanner(System.in);  

        int n = sc.nextInt(); //집의 수  

        int[] dp =new int[n+1];  
        int[][] arr = new int[n+1][3];  
        int index = 4;  


        for(int i=1; i<=n; i++){  
            for(int j=0; j<3; j++){  
                arr[i][j] = sc.nextInt();  
            }  
        }  

        for(int i=1; i<=n; i++){  
            dp[i] = Integer.MAX_VALUE;  

            for(int j=0; j<3; j++){  
                if(index != j){  
                    dp[i] = Math.min(dp[i], arr[i][j]);  
                    index = j;  
                }  
            }  
        }  

        int result = 0;  

        for(int i=1; i<=n; i++){  
            result += dp[i];  
        }  

        System.out.println(result);  
        sc.close();  
    }  
}

실패..!

이렇게 작성하고 돌려보니 문제가 있었다.

if(index != j){  
    dp[i] = Math.min(dp[i], arr[i][j]);  
    index = j;  
}  

여기서 무조건 첫번째 부터 돌며 1번집의 최솟값을 갖게되며 시작한다. 하지만 1번집에서 는 최솟값이, 전체적으로 봤을때 최솟값을 보장하지 않는다. 이를 해결하기 위해서는

각집의 최솟값을 구해 누적합을 구하는 것이 아닌, 모든 경로의 수를 찾아서 최종적으로 작은 누적합을 찾아야 한다.

//Red일 경우
Cost[N][0] = min( Cost[N-1][1], Cost[N-1][2] ) + Cost[N][0]

//Green일 경우
Cost[N][1] = min( Cost[N-1][0], Cost[N-1][2] ) + Cost[N][1]

//Blue일 경우
Cost[N][2] = min( Cost[N-1][0], Cost[N-1][1] ) + Cost[N][2]

두번째 시도

import java.util.Scanner;

public class Main {

    static int Red = 0;
    static int Green = 1;
    static int Blue = 2;

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt(); //집의 수

        int[][] arr = new int[n][3];

        for(int i=0; i<n; i++){
            arr[i][Red] = sc.nextInt();
            arr[i][Green] = sc.nextInt();
            arr[i][Blue] = sc.nextInt();
        }

        for(int i=1; i<n; i++){
            arr[i][Red] += Math.min(arr[i - 1][Green], arr[i - 1][Blue]);
            arr[i][Green] += Math.min(arr[i - 1][Red], arr[i - 1][Blue]);
            arr[i][Blue] += Math.min(arr[i - 1][Red], arr[i - 1][Green]);
        }

        //n-1까지 구해놓고 마지막으로 그들중 최솟값을 구해준다.
        //arr에는 누적합이 쌓여있는것이다.

        System.out.println(Math.min(Math.min(arr[n-1][Red], arr[n-1][Green]),arr[n-1][Blue]));
        sc.close();
    }
}

이렇게 작성해서 성공!