21.07.21 - [BOJ] 1149. RGB 거리

[suhyunsim]

문제

• 1149

핵심 아이디어

• 각 집을 빨강으로 칠할 때 드는 비용,초록으로 칠할 때 드는 비용,파랑으로 드는 비용이 주어질 때,모든 집을 칠하는 비용의 최솟값을 구하는 문제
• 0: 빨, 1: 초, 2: 파
• A[i][j]: i번 집을 j번색으로 칠하는 비용
• 집 i의 이웃은 집 i-1과 집 i+1이고(연속), 첫 집과 마지막 집은 이웃이 아니다.
  • 집 i는 i-과 색을 다르게 칠하기 -> 모든 이웃은 같은 색으로 칠하지 않음
• D[i][j]=i번 집을 색 j로 칠했을 때, 1~i번 집을 칠하는 비용의 최소값
• D[i][0] = min(D[i - 1][1], D[i - 1][2]) + A[i - 1][0]
• D[i][1] = min(D[i - 1][0], D[i - 1][2]) + A[i - 1][1]
• D[i][2] = min(D[i - 1][0], D[i - 1][1]) + A[i - 1][2]
  => min(D[n][0], D[n][1], D[n][2])

어려운 점, 실수

풀이

package main.java.com.poogle.BOJ.Q1149;

import java.util.Scanner;

public class Main {
    static int[][] d;
    static int[][] a;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        d = new int[n + 1][3];
        a = new int[n + 1][3];
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < 3; j++) {
                a[i][j] = sc.nextInt();
            }
        }
        for (int i = 1; i <= n; i++) {
            d[i][0] = Math.min(d[i - 1][1], d[i - 1][2]) + a[i][0];
            d[i][1] = Math.min(d[i - 1][0], d[i - 1][2]) + a[i][1];
            d[i][2] = Math.min(d[i - 1][0], d[i - 1][1]) + a[i][2];
        }
        System.out.println(Math.min(Math.min(d[n][0], d[n][1]), d[n][2]));
    }
}