[백준/DP] 1149번 RGB거리 (JAVA)

문제

---

풀이

• cost: 주어진 집 칠하는 비용
• dp: i번째 집을 color로 칠할 때의 최소 비용

i번째 집을 color로 칠하려면, 바로 앞 집을 칠하는 비용에 현재 집 칠하는 비용 costs[i][color]을 더하면 된다. 이 때 앞 집을 칠하는 비용은 현재 칠하고자 하는 color를 제외한 다른 두 색의 dp[i-1][otherColor] 값 중 더 작은 값이다.

이를 코드로 표현하면 아래와 같다.

코드

import java.io.*;

public class Main {

    private static final int MAXIMUM = 1000;
    private static final int RED = 0;
    private static final int GREEN = 1;
    private static final int BLUE = 2;
    private static final int COLORS = 3;

    private static int n;
    private static int[][] costs = new int[MAXIMUM + 1][COLORS];
    private static int[][] dp = new int[MAXIMUM + 1][COLORS];

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

        n = Integer.parseInt(br.readLine());
        for (int i = 1; i <= n; i++) {
            String[] chunks = br.readLine().split(" ");
            costs[i][RED] = Integer.parseInt(chunks[RED]);
            costs[i][GREEN] = Integer.parseInt(chunks[GREEN]);
            costs[i][BLUE] = Integer.parseInt(chunks[BLUE]);
        }

        dp();
        bw.append(String.valueOf(Math.min(Math.min(dp[n][RED], dp[n][GREEN]), dp[n][BLUE])));

        br.close();
        bw.close();
    }

    private static void dp() {
        dp[1][RED] = costs[1][RED];
        dp[1][GREEN] = costs[1][GREEN];
        dp[1][BLUE] = costs[1][BLUE];
        for (int i = 2; i <= n; i++) {
            dp[i][RED] = costs[i][RED] + Math.min(dp[i - 1][GREEN], dp[i - 1][BLUE]);
            dp[i][GREEN] = costs[i][GREEN] + Math.min(dp[i - 1][RED], dp[i - 1][BLUE]);
            dp[i][BLUE] = costs[i][BLUE] + Math.min(dp[i - 1][RED], dp[i - 1][GREEN]);
        }
    }
}

이것도 저번(2020년 7월)에 풀었던 문제다. 다시 DP를 제대로 공부하고자 머리를 굴리면서 문제를 보니까, 저번과는 느낌이 사뭇 달랐다. 다른 사람 풀이에 의존하지 않고 진짜 내가 다시 푸는 게 제일 중요하다는 걸 실감하고 있다.