백준 1149번 RGB거리 [JAVA]

문제

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

출력

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

 

 

 

 

 

문제이해

집이 n개가 있다 
1번 집부터 n번 집까지 순서대로 있다
n번집은 n-1집의 색과 같지 않아야 한다(이전 집과만 색이 다르면 된다)

입력
첫쨰줄 : n-> 집의수
둘째 줄부터 N개의 줄: 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다

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

알고리즘 설계

일단 각 집의 어떤 색으로 칠하고 그 색으로 칠하면 얼마나 비용이 드는지 
이차원 배열 list[][]에 담는다
0=빨 
1=초
2=파 라고 했을때
ex) list[1][0] -> 첫번째 집을 빨간색으로 칠했을때 드는 비용 

점화식 정의: 
1. dp[n][0] -> n개의 집 중에서 마지막 집을 빨간색으로 칠했을때 n개의 집을 색칠하는 비용의 최솟값
=min(dp[n-1][1],dp[n-1][2])+list[n][0]이다
 
2. dp[n][1] -> n개의 집 중에서 마지막 집을 초록색으로 칠했을때 n개의 집을 색칠하는 비용의 최솟값
=min(dp[n-1][0],dp[n-1][2])+list[n][0]이다 

3. dp[n][2] -> n개의 집 중에서 마지막 집을 파랑색으로 칠했을때 n개의 집을 색칠하는 비용의 최솟값
=min(dp[n-1][0],dp[n-1][1])+list[n][0]이다 

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][3];
        int [][]dp=new int[n+1][3]; 
        for(int i=1;i<=n;i++){   
            for(int j=0;j<3;j++){  
                list[i][j]=sc.nextInt();
            }
        }

        dp[1][0]=list[1][0];
        dp[1][1]=list[1][1];
        dp[1][2]=list[1][2];

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


        int min=dp[n][0];
        if(min>dp[n][1])
            min=dp[n][1];
        if(min>dp[n][2])
            min=dp[n][2];


        System.out.println(min);



    }
}

      
느낀점:

1. 식상한 말이지만 점화식을 어떻게 세우냐가 문제 해결의 90프로이상을 차지한다 

2. 그리고 DP문제는 보통 배열로 푸는데  무조건 1가지 종류의 배열(보통 배열이름: dp)로만 풀어야된다고 착각하면 오해다 

3. 그리고 for문으로 dp배열의 값을 채울때 문제에서 요구하는 값까지만 채우면 된다

4. "이전값은 현재값의 x를 제외한 y와 z만 올수있다." 느낌의 문제는 모두 이차원 배열로 풀이할수 있다  

 

점화식 세우는 tip

 

1. 일단 적당한 수를 넣어서 대강 감이 잡히는 대로 점화식을 세워본다 

2. 감으로 잡아본 점화식에 0혹은 1부터 수를 늘리면서 넣어보면 규칙이 나온다=> 그러면 점화식이 완벽하게 잡힌다  

3. 문제마다 다르지만 n=0,1,2인 case는 점화식조건으로 풀이되지않을수 있다 why? 

ex) n=1일때 dp[n]=dp[n-1]+dp[n-2]인 경우 인덱스오류가 발생하므로 이 경우에 n=0,n=1일때는 먼저 초기화 해놓고 푼다

 

위 문제의 경우 n=1일때는 초기화 해놨다

dp[1][0]=list[1][0];
dp[1][1]=list[1][1];
dp[1][2]=list[1][2];