문제

아이디어

DP 문제인 1149: RGB 거리와 유사한 문제다.
차이점이라면, 이 문제에는 첫번째 집과 N번째 집의 색이 달라야 한다.
1149: RGB 거리와 동일하게 푼다면, 첫번째 집과 N번째 집이 겹치는 경우를 잡지 못한다.

사실 응용이 필요한 문제 같지만, 간단하게 풀 수 있다.
N <= 1000 이므로 그냥 DP를 세 번 돌려서 최솟값을 찾으면 된다.

첫 집이 빨간색인 경우, 초록색인 경우, 파란색인 경우 각각 구해서 DP로 풀어준다면 뚝딱이다.

소스 코드

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

public class Main {
    static StringTokenizer st;
    static int n;
    static int[][] house;
    static int[][][] dp;
    static int ans = Integer.MAX_VALUE;

    // 0 -> R로 시작
    // 1 -> G로 시작
    // 2 -> B로 시작

    static void getDP(int color) {
        for (int i = 0; i < n; i++) {
            Arrays.fill(dp[color][i], 1000 * 1000);
        }

        dp[color][0][color] = house[0][color];

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

        dp[color][n - 1][color] = Integer.MAX_VALUE;

        ans = Math.min(ans, Math.min(dp[color][n - 1][0], Math.min(dp[color][n - 1][1], dp[color][n - 1][2])));
    }


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());
        house = new int[n][3];
        dp = new int[3][n][3];

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            house[i][0] = Integer.parseInt(st.nextToken());
            house[i][1] = Integer.parseInt(st.nextToken());
            house[i][2] = Integer.parseInt(st.nextToken());
        }

        getDP(0);
        getDP(1);
        getDP(2);

        System.out.println(ans);
    }
}

채점 결과

백준 서버가 이상한지 제출 후에 채점까지 시간이 걸렸다.