[Algorithm][파이썬] 백준 17404번: RGB거리 2

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

17404번: RGB거리 2

 

---

문제

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

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때,

아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

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

 

입력

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다.

둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다.

집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

 

출력

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

 

코드

코드 출처: https://sangbeomkim.tistory.com/8

참고 링크: https://moz1e.tistory.com/51

/* 첫 번째 집(1)과 마지막 집(N)의 색이 달라야 하므로 N의 색을 알기 위해선 
1의 색이 달라야 한다. 따라서 1이 다른 색으로 선택되지 않도록 함으로써 1의 색을 고정시킨다 */

import java.util.*;
public class Main {
    public static void main(String[] args){
        Scanner in=new Scanner(System.in);
        int n = in.nextInt();
        int[][]list=new int[n+1][n+1];  //페인트 칠 비용 입력
        int[][]dp=new int[n+1][n+1]; //0:빨강 1:초록 2:파랑  
        int[]paint=new int[n+1]; //첫 집의 색깔에 따라 나오는 최소 비용

        for(int i=1;i<=n;i++) {
            for (int j = 0; j < 3; j++) {
                list[i][j] = in.nextInt();
            }
        }
        
        //첫 집 색칠
        for(int i=0;i<3;i++) { 
            for (int j = 0; j < 3; j++) { 
                if (i == j)
                    dp[1][j] = list[1][j]; //첫 집에 i색 색칠
                else
                    dp[1][j] = 1001; //나머지 색은 색칠 X
            }

            //두 번째 집부터 색칠
            for (int k = 2; k < n + 1; k++) {
                dp[k][0] = Math.min(dp[k - 1][1], dp[k - 1][2]) + list[k][0];
                dp[k][1] = Math.min(dp[k - 1][0], dp[k - 1][2]) + list[k][1];
                dp[k][2] = Math.min(dp[k - 1][0], dp[k - 1][1]) + list[k][2];
                if(k==n){     //마지막 집은 첫 집이랑 색깔이 달라야 함
                    if(i==0){ //첫 집이 빨간색일 경우, 마지막 집은 초록 OR 파랑
                        paint[i]=Math.min(dp[n][1],dp[n][2]);
                    }
                    if(i==1){ //첫 집이 초록색일 경우, 마지막 집은 빨강 OR 파랑
                        paint[i]=Math.min(dp[n][0],dp[n][2]);
                    }
                    if(i==2){ //첫 집이 파랑색일 경우, 마지막 집은 초록 OR 빨강
                        paint[i]=Math.min(dp[n][0],dp[n][1]);
                    }

                }
            }

        }

        //이중에서 최솟값 = 페인트 최소 비용
        System.out.print(Math.min(paint[0],Math.min(paint[1],paint[2])));
    }
}

너무 어려워서 결국 구글링했음에도 아직까지 코드를 완전히 이해하지 못했다.

코드를 완전히 이해할 수 있을 때까지 더 열심히 공부해야 겠다...