링크

1149 RGB거리

문제

풀이

top down으로 풀었다.

0번집에서 색 1번과 2번을 칠한거에 최솟값,
1번집에서 색 0번과 2번을 칠한거에 최솟값,
2번집에서 색 0번과 1번을 칠한거에 최솟값

그렇게 dp에 저장하고 재귀를 실행시키는 Top-down에서 0번째 집에서 0번색, 1번색, 2번색 스타트를 해서 가장 작은 값을 도출하면 된다.

코드

import java.awt.desktop.PreferencesEvent;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.nio.Buffer;
import java.sql.Array;
import java.util.*;

public class Main {
    public static int n;
    public static int[][] dp;
    public static int[][] arr;

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

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

        for(int i=0;i<n;i++){
            String[] element = br.readLine().split(" ");

            for(int j=0;j<element.length;j++){
                arr[i][j] = Integer.parseInt(element[j]);
            }
        }

        for(int i=0;i<dp.length;i++){
            Arrays.fill(dp[i], -1);
        }

        //집 3군데에서 스타트 해서 가장 작은 값 출력
        System.out.println(Math.min(TopDown(0, 0), Math.min(TopDown(0, 1), TopDown(0, 2))));

//        for(int i=0;i<dp.length;i++) System.out.println(Arrays.toString(dp[i]));
    }

    public static int TopDown(int dept, int house){
        if(dept == n){
            return 0;
        }

        if(dp[dept][house] != -1){
            return dp[dept][house];
        }

        //house가 0번집일때
        int case1 = Integer.MAX_VALUE;
        if(house == 0)
            case1 = Math.min(TopDown(dept+1, 1), TopDown(dept+1, 2));

        //house가 1번집일때
        int case2 = Integer.MAX_VALUE;
        if(house == 1)
            case2 = Math.min(TopDown(dept+1, 0), TopDown(dept+1, 2));

        //house가 2번집일때
        int case3 = Integer.MAX_VALUE;
        if(house == 2)
            case3 = Math.min(TopDown(dept+1, 0), TopDown(dept+1, 1));

        if(case1 != Integer.MAX_VALUE && case2 != Integer.MAX_VALUE && case3 != Integer.MAX_VALUE) return 0;

        dp[dept][house] = Math.min(case1, Math.min(case2, case3)) + arr[dept][house];

        return dp[dept][house];
    }
}