RGB거리

📍 문제 설명

 

💡 접근

첫번째에 작은 값을 선택했을 때 최종 값이 최솟값이 되는지 보장할 수 없으므로 그리디 방식으로는 못푼다.

2차원 배열을 이용하여 n번째 항에 각 색깔을 칠했을 때의 최소 비용을 각각 넣는다.

마지막에 들어가 있는 값들 중 최솟값이 모든 집을 칠하는 비용의 최솟값이다.

 

👩‍💻 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int n, m, answer = Integer.MAX_VALUE, max, k, min;
    static int[][] board;
    static int[][] arr, dp, t, p;
    static boolean[][] visited;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static ArrayList<String> list = new ArrayList<>();
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        Scanner kb = new Scanner(System.in);
        Main T = new Main();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = kb.nextInt();
        board = new int[n][3];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < 3; j++) {
                board[i][j] = kb.nextInt();
            }
        }
        dp = new int[n][3];

        T.solution();
        System.out.println(answer);
    }

    private void solution() {
        dp[0][0] = board[0][0];
        dp[0][1] = board[0][1];
        dp[0][2] = board[0][2];
        for(int i = 1; i < n; i++) {
            dp[i][0] = Math.min(board[i][0] + dp[i-1][1], board[i][0] + dp[i-1][2]);
            dp[i][1] = Math.min(board[i][1] + dp[i-1][0], board[i][1] + dp[i-1][2]);
            dp[i][2] = Math.min(board[i][2] + dp[i-1][0], board[i][2] + dp[i-1][1]);
        }

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

}