#백준_1149 RGB거리 - Java 자바

#유형 : 다이나믹 프로그래밍

#난이도 : 실버 1

#조건은 다음과 같다

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

요약하면 인접한 집은 색이 같으면 안된다는 것이다. 아래와 같은 사항을 dp로 풀어내면 된다.

1. 전에 빨강을 칠했다 => 파랑,초록

2. 전에 파랑을 칠했다 => 빨강,초록

3. 전에 초록을 칠했다 => 빨강,파랑 

 

 

dp[i][1]이 빨강색이라고 가정하면, 그 전에는 파랑,초록을 칠해야 한다. 따라서 dp[i-1][2](파랑), dp[i-1][3](초록) 둘 중 한개에서 빨강의 값을 더해주는 것이다.

 

즉 아래와 같이 dp를 풀어내면 된다.

dp[i][1] = Math.min(dp[i-1][2], dp[i-1][3]) + arr[i][1];

dp[i][2] = Math.min(dp[i-1][1], dp[i-1][3]) + arr[i][2];

dp[i][3] = Math.min(dp[i-1][1], dp[i-1][2]) + arr[i][3];

package bj;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class p1149 {
    static int N;
    static int arr[][];
    static int dp[][];
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new int[N+1][N+1];
        dp = new int[N+1][N+1];
        for(int i=1; i<=N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=1; j<=3; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        // 0 : 빨강, 1 : 파랑, 2 : 초록
        int result = solve();
        
        System.out.println(result);
    }
    private static int solve() {
        // TODO Auto-generated method stub
        // 0 : 빨강, 1 : 파랑, 2 : 초록 
        dp[1][1] = arr[1][1];
        dp[1][2] = arr[1][2];
        dp[1][3] = arr[1][3];
        
        //1번 집의 색은 2번 집의 색과 같지 않아야 한다.
        //N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
        //i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.
        // 요약하면 인접한 집은 색이 같으면 안된다는 것 => 1. 전에 빨강을 칠했다 => 파랑,초록 // 2. 전에 파랑을 칠했다 => 빨강,초록 // 3. 전에 초록을 칠했다 => 빨강,파랑 
        for(int i=2; i<=N; i++) {
            dp[i][1] = Math.min(dp[i-1][2], dp[i-1][3]) + arr[i][1];
            dp[i][2] = Math.min(dp[i-1][1], dp[i-1][3]) + arr[i][2];
            dp[i][3] = Math.min(dp[i-1][1], dp[i-1][2]) + arr[i][3];
        }
        int rs = Integer.MAX_VALUE;
        
        for(int i=1; i<=3; i++)
            rs = Math.min(rs, dp[N][i]);
        
        return rs;
    }
}