백준 17404 RGB거리 2 Java [DP]

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

17404번: RGB거리 2

 

 

저번에 풀었던 RGB거리 문제와 비슷하지만 N번 집과 1번 집이 다른 색으로 칠해져야하는 조건이 추가됐다

첫번째 집에 칠하는 색에 따라 dp를 따로 해서 마지막 줄에서 다른 색 비용을 더한 값 중에서 최소값들을 비교해주면 된다

첫 두줄을 미리 계산하고 다음 줄부터 dp를 해줬다

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

public class Main {
    static final int INF = 2_000_000;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[][] dp = new int[3][3];
        int[] arr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int[] next = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int result = INF;
        for (int i = 0; i < 3; i++) {
            dp[i] = next.clone();
            dp[i][i] += INF;
            for (int j = 0; j < 3; j++) dp[i][j] += arr[i];
        }
        for (int n = 2; n < N; n++) {
            arr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            for (int i = 0; i < 3; i++) {
                int[] now = new int[3];
                for (int j = 0; j < 3; j++) {
                    now[j] = arr[j] + Math.min(dp[i][(j+1)%3], dp[i][(j+2)%3]);
                }
                dp[i] = now;
            }
        }
        for (int i = 0; i < 3; i++) {
            int cost = Math.min(dp[i][(i+2)%3], dp[i][(i+1)%3]);
            result = Math.min(result, cost);
        }
        System.out.println(result);
    }
}