백준 17404번 RGB거리 2 [JAVA]

문제

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보다 작거나 같은 자연수이다.

출력

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

 

 

 

이 문제도 어려웠다 처음에는 쉬울줄 알았는데 답이 계속 이상하게 나왔다 

RGB문제는 간단하게 dp[n][m]을 n번 집까지 색칠했는데 n번집을 m색으로 칠했을경우 나올수 있는 페인트 비용의 최솟값으로 설정해서 풀면되는데

이 문제는 첫번째 집과 마지막집도 같은색이면 안되게 해야된다

 

 

알고리즘 설계

 

1. 첫집에 색칠할 색깔을 정해놓는다 

0:빨강 1:초록 2:파랑

 

dp[1][0] => 첫집을 빨간색으로 칠해놓는다 dp[1][0]=list[1][0]

그러면 나머지 색깔로는 첫집을 색칠할수 없으므로

dp[1][1],dp[1][2]는 색칠할때 드는 비용이 n<=1000이므로 1001로 초기화 해놓는다 (최솟값 구하는것이므로 아예 선택 안되게 만들기 위해)

 

 

dp[1][1] => 첫집을 초록색으로 칠해놓는다 dp[1][1]=list[1][1]

그러면 나머지 색깔로는 첫집을 색칠할수 없으므로

dp[1][0],dp[1][2]는 색칠할때 드는 비용이 n<=1000이므로 1001로 초기화 해놓는다 (최솟값 구하는것이므로 아예 선택 안되게 만들기 위해)

 

 

dp[1][2] => 첫집을 빨간색으로 칠해놓는다 dp[1][2]=list[1][2]

그러면 나머지 색깔로는 첫집을 색칠할수 없으므로

dp[1][0],dp[1][1]는 색칠할때 드는 비용이 n<=1000이므로 1001로 초기화 해놓는다 (최솟값 구하는것이므로 아예 선택 안되게 만들기 위해)

 

 

 

2. 두번쨰집부터 색칠을한다 

   단 마지막집은 첫집이랑 같은 색을 칠할수 없으므로 dp[마지막집][첫집색칠한 색깔]은 고려하지않는다

 

 

import java.util.*;
public class Main {
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[][]list=new int[n+1][n+1];  //페인트 칠 비용 입력
        int[][]dp=new int[n+1][n+1]; //  0:빨강 1:초록 2:파랑  ex) dp[2][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] = sc.nextInt();
            }
        }

        for(int i=0;i<3;i++) {    //이번에는 첫집에 i색을 칠하겠어요
            for (int j = 0; j < 3; j++) { //색깔들은 준비해주세요
                if (i == j)
                    dp[1][j] = list[1][j]; // 예정대로 첫집에 i색을 칠하겠어요
                else
                    dp[1][j] = 1001; //나머지 색은 색칠안해요 (완전 논외로 취급)
            }

            //이제 2번째 집 부터 색칠해줄게요
            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){ //첫집에 빨간색을 칠했을경우 마지막은 초록 아님 파랑
                        paint[i]=Math.min(dp[n][1],dp[n][2]);
                    }
                    if(i==1){ //첫집에 초록색을 칠했을경우 마지막은 빨강 아님 파랑
                        paint[i]=Math.min(dp[n][0],dp[n][2]);
                    }
                    if(i==2){ //첫집에 파랑색을 칠했을경우 마지막은 빨강 아님 초랑
                        paint[i]=Math.min(dp[n][0],dp[n][1]);
                    }

                }
            }

        }

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