[자바] 백준 1149번 RGB거리 2021-06-21

우선, '비용의 최솟값' 을 구하라는 말이 나왔으므로, DP로 풀어야 한다. 그런데 그 전까지는 DP배열이 1차원 배열이였는데 지금은 상황이 조금 다르고, DP[i][j]가 무엇을 가르키는지 구체적으로 정의하는 것이 매우 중요하다.
이전 포스트에서도 꾸준히 강조하는 말하지만 DP문제에서 무엇을 DP값으로 정할건지가 핵심이다.
나는 이 문제에서 2차원 배열로 주어진 입력값(행:N번째 집 열: 빨,초파)에서 결국 맨 마지막으로 선택되어질수 있는 색깔, 마지막 N번쨰 항에을 조건으로 삼아 DP값을 정의하였다. 우선 문제의 특수한 조건들 때문에 마지막 N번집의 색깔은 빨, 초, 파, 중 한개만 가능하다. 즉, 경우의 수를 3개로 나누어(마지막 색이 빨강부터 칠해질건지, 파랑부터 칠해질건지..) 모든 경우의 수를 구한 다음, 각 인덱스마다, 최소의 비용을 DP배열에 저장한다. 예를들면 DP[2][2]의 값은 3번째 집까지 최소의 비용으로 칠해나갈때, 마지막 칠해진 색깔이 '파랑 일때의 값'이다.
즉,
DP[2][0] : 3번째 집의 색이 빨강색이고, 해당집까지최소의 비용으로 칠했을때,의 비용.
DP[2][1] : 3번째 집의 색이 초록색이고, 해당집까지 최소의 비용으로 칠했을떄의 비용.
DP[2][2] : 3번째 집의 색이 파랑색이고, 해당집까지 최소의 비용으로 칠했을때의 비용.

이렇게 DP[i][j] 의 의미는 0부터 i번째 집까지, 마지막 색이(N번째항)이 j색깔일때의 최솟값이다.

0부터 N번쨰 인덱스까지의 최소/최대값 : DP[N]

 

 내가 이전 DP문제들을 계속 풀며, 얻은 진리이다. 문제에서는 "N"의 최소값과 최대값을 구하라면, DP[N]을 그대로 출력해주면 되지만, 만약 마지막 경우의 수가 될수 있는 여러개중(빨초파) 최대로 되는 경우(이문제)나, 가장 긴 증가하는 부분수열과 같이, N번째 항까지의 최댓값은 맞지만 그보다 더 큰 최댓값이 다른 DP인덱스에서 있을수 있는 경우는, 모든 DP의 값들중, 최댓값을 구해주면 된다.

ex) dp[2]=7, dp[3]=5 : 0부터 3까지 조건을따라 구한 최대의 값이 5인건 맞지만, 그전, 0부터 2까지 조건을 따라 구한 최대의 값 7 이 더 큰 경우 <-이런 형태가 증가하는 부분수열 문제임.

처음 DP문제를 풀때는 정말 답도없고, DP배열의 의미에 대해서 막막했는데, 점점 문제경험과 프로그래밍 시간을 투자하다보니, 이런 진리도 알게되었다... 나 자신이 너무 자랑스럽고 뿌듯하다.

*추신
DP[0]값은 저장해놓고, for문을 [1]부터 시작하는 것을 잊지말자. 즉 예를 들면 피보나치 수열의 점화식이 dp[N]=dp[N-2]+dp[N-1]이면, for 반복문을 통해 dp배열을 채워주기 위해선 dp[0],dp[1]값이 미리 들어가 있어야 한다.

import java.util.Scanner;

public class Main {


    public static void main(String[] args){
        Scanner s = new Scanner(System.in);
        int n=s.nextInt();
        int[][] arr=new int[n][3];
        int[][] dp=new int[n][3];
        for (int i = 0; i < n; i++) {
            for(int j=0;j<3;j++){
                arr[i][j]=s.nextInt();
            }



        }
            for (int i = 0; i < 3; i++) {
                dp[0][i]=arr[0][i];
                //첫번째 dp 값은 각 색깔별로 첫번째 arr값이랑 같으므로 그대로 입력한다.
                //*중요 항상 dp의 첫 값은 미리 입력해 놔야함.
            }
        for (int i = 1; i < n; i++) {
            for(int j=0;j<3;j++){
                if(j==0){
                    dp[i][j]=arr[i][j]+Math.min(dp[i-1][1],dp[i-1][2]);
                }
                else if(j==1){
                    dp[i][j]=arr[i][j]+Math.min(dp[i-1][0],dp[i-1][2]);

                }
                else if(j==2){
                    dp[i][j]=arr[i][j]+Math.min(dp[i-1][0],dp[i-1][1]);
                }

            }
        }
        int min=Integer.MAX_VALUE;
            for(int i=0;i<3;i++){
                min=dp[n-1][i]<min?dp[n-1][i]:min;
                // 맨 n번째 집까지 각 색깔별로 최소의 비용을 구했을때
                //3색중 가장 최소의 비용을 출력.
            }
        System.out.println(min);

        }
    }

공부시간 : 2시간.
순공부시간 1시간.