백준 - RGB거리 2(17404번) - Java

1. 문제

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

2. 풀이

참고 풀이

1번집은 2번집, N번집과 색이 같지 않아야하고,
N번집은 N-1번집, 1번집과 색이 같지 않아야 한다.

글로 보면 어려웠는데 생각해보니 기존 RGB거리 문제(https://www.acmicpc.net/problem/1149) 에서 추가로 1번집과 N번집이 같지 않다는 것이다.

따라서 이는 추가로

• 1번집을 R, G, B로 각각 색칠할 경우의 DP에서
  N번집 집이 R, G, B각각이 아닌 경우의 MIN값을 구해주면 된다.

✨핵심 Point

코드를 작성하면서 max값을 설정하는게 중요하다. 즉 아얘 나올 수 없는 값을 설정해줘야 하는것이다. 만일 Integer.MAX_VALUE를 하게되면 overflow가 발생할 수도 있으니 주의하자.
그냥 단순히 1001이라고 생각할 수 있지만, 이는 충분히 덧셈 결과에서 뒤집을 수 있는 크기이기 때문에 계산결과가 틀릴 수도 있다.
max = 1000 * 1000 + 1이다.

3. 코드

import java.util.*;
import java.io.*;

public class Main {
    
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int N = Integer.parseInt(br.readLine());
        
        int arr[][] = new int[N][3];
        int max = 1000*1000 + 1; // 모든 경우의 수 중에서 가장 큰 값...
        int answer = max;
        
        for(int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
            arr[i][2] = Integer.parseInt(st.nextToken());
        }
        
        for(int start = 0; start <= 2; start++) {
            int dp[][] = new int[N][3];
            
            for(int j = 0; j <= 2; j++) {
                if(start == j) {
                    dp[0][start] = arr[0][start];
                } else {
                    dp[0][j] = max;
                }
            }
            
            for(int i = 1; i < N; i++) {
                dp[i][0] = Math.min(dp[i-1][1], dp[i-1][2]) + arr[i][0];
                dp[i][1] = Math.min(dp[i-1][0], dp[i-1][2]) + arr[i][1];
                dp[i][2] = Math.min(dp[i-1][0], dp[i-1][1]) + arr[i][2];
            }
            
            for(int j = 0; j <= 2; j++) {
                if(start != j){
                    answer = Math.min(answer, dp[N-1][j]);
                }
            }
        }
        
        System.out.println(answer);
        
    }
}