[백준 1149번] RGB거리

문제 링크: 1149번 RGB거리

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

 

DP 문제이다. 연속된 집은 같은 색깔로 칠할 수 없으므로, i번째 집까지의 최솟값 mem[i] 중에서도 i번째 집이 RED일 때의 최솟값 mem[i][RED]는, i-1번째 집까지의 최솟값 mem[i-1] 중에서도 i-1번째 집이 GREEN일 때의 최솟값(mem[i][GREEN])과 i-1번째 집이 BLUE일 때의 최솟값(mem[i][BLUE])에 i번째 집을 RED로 칠할 때의 비용(arr[i])을 더한 것이다. 이처럼 mem[i]는 i번째 집의 색깔에 따라 세 개의 값을 저장하고 있어야 한다.

 

import java.util.Scanner;

public class Main {
    static int RED = 0;
    static int GREEN = 1;
    static int BLUE = 2;
    static int n;
    static int[][] arr;
    static int[][] mem;

    public static int min(int a, int b) {
        if (a < b) return a;
        return b;
    }

    public static int min(int a, int b, int c) {
        if (a <= b && a <= c) return a;
        else if ( b <= a && b <= c ) return b;
        return c;
    }

    public static int paint(int n) {
        mem[0][RED] = mem[0][GREEN] = mem[0][BLUE] = 0;

        for (int i = 1; i <= n; i++) {
            mem[i][RED] = min(mem[i-1][GREEN], mem[i-1][BLUE]) + arr[i][RED];
            mem[i][GREEN] = min(mem[i-1][RED], mem[i-1][BLUE]) + arr[i][GREEN];
            mem[i][BLUE] = min(mem[i-1][RED], mem[i-1][GREEN]) + arr[i][BLUE];
        }

        return min(mem[n][RED], mem[n][GREEN], mem[n][BLUE]);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();

        arr = new int[n+1][3];
        mem = new int[n+1][3];

        for (int i = 1; i <= n; i++) {
            arr[i][0] = sc.nextInt();
            arr[i][1] = sc.nextInt();
            arr[i][2] = sc.nextInt();
        }

        int res = paint(n);
        System.out.println(res);

        sc.close();
    }
}