RGB 거리 - 1149

문제

풀이

처음 풀이

import java.util.Scanner;

// RGB 거리 - S1 - DP
public class ex1149 {
    static int n;
    static int[][] arr;
    static int[] dp = new int[1001];
    static int min=Integer.MAX_VALUE;
    static int idx=0;

    public static int solution(){
        for(int i=0; i<3; i++){
            if(arr[0][i] < min){
                min = arr[0][i];
                idx=i;
            }
        }

        dp[0]=min;
        min = Integer.MAX_VALUE;

        for(int i=1; i<n; i++){
            for(int j=0; j<3; j++){
                arr[i][idx]=101;
                if(arr[i][j]<min){
                    min = arr[i][j];
                    idx = j;
                }
            }
            dp[i] = dp[i-1] + min;
            min=Integer.MAX_VALUE;
        }

        return dp[n-1]; // 최소합
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        arr = new int[n][3];

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

테스트케이스만 보면서 구현. 테스트케이스는 통과한다만 실패. 막구현 하지말자 제발.
아아 DP어렵다... ; 인터넷 풀이를 봐도 이해 안되는게 대부분

해결 풀이

import java.util.Scanner;

// RGB 거리 - S1 - DP
public class ex1149 {

    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][0] = sc.nextInt(); // R
            arr[i][1] = sc.nextInt(); // G
            arr[i][2] = sc.nextInt(); // B
        }

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

        System.out.println(Math.min(Math.min(arr[n-1][0],arr[n-1][1]) ,arr[n-1][2]));


    }
}

이 문제의 핵심

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

해결 방법
R G B 각각의 색 경우에 따른 최솟값을 구해서 더해가면서 나아가야한다.

R을 기준으로 현재 i의 이전까지의 최소값들의 합(i-1)중에서 G와 B중에서 더 최솟값인 경우를 현재 i의 R위치에 더한다. 이런 식으로 다른 색깔의 경우에도 계산해주며, 최종적으로는 배열 마지막 위치에는 각 색별로 가장 작은 값을 가진 값이 정답이다.

DP 개어렵다