[백준] RGB거리 1149번 JAVA

주어진 조건을 만족하면서 각 집을 빨강, 초록, 파랑으로 칠하는 비용을 최소화하는 문제입니다. 각 집을 어떤 색으로 칠할 때 이전 집과 인접한 집의 색이 달라야 하며, 그에 따른 최소 비용을 구해야 합니다.

입력 처리: 집의 수와 각 집을 칠하는 비용을 2차원 배열에 저장합니다.

int N = Integer.parseInt(br.readLine());
int[][] arr = new int[N][3];
for(int i = 0; i < arr.length; i++){
    String[] input = br.readLine().split(" ");
    arr[i][0] = Integer.parseInt(input[0]);
    arr[i][1] = Integer.parseInt(input[1]);
    arr[i][2] = Integer.parseInt(input[2]);
}

DP 테이블 초기화: 첫 번째 집을 빨강, 초록, 파랑으로 칠할 때의 비용을 그대로 저장합니다.

int[][] dp = new int[N][3];
dp[0][0] = arr[0][0];
dp[0][1] = arr[0][1];
dp[0][2] = arr[0][2];

DP 점화식: 두 번째 집부터 시작해서 각 집을 칠하는 최소 비용을 계산합니다. i번째 집을 빨강으로 칠할 때는 이전 집이 초록이거나 파랑이어야 하므로, dp[i - 1][1]과 dp[i - 1][2] 중 작은 값에 현재 칠하는 비용을 더해주면 됩니다.

for(int i = 1; i < N; i++){
    dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + arr[i][0]; // 빨강
    dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + arr[i][1]; // 초록
    dp[i][2] = Math.min(dp[i - 1][0], dp[i - 1][1]) + arr[i][2]; // 파랑
}

결과 도출: 마지막 집을 빨강, 초록, 파랑으로 칠할 때의 최소 비용 중 가장 작은 값을 출력합니다.

int result = Math.min(Math.min(dp[N - 1][0], dp[N - 1][1]), dp[N - 1][2]);
bw.write(result + "\n");

전체 코드는 이렇습니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

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

        int N = Integer.parseInt(br.readLine());

        int[][] arr = new int[N][3];

        for(int i = 0; i < arr.length; i++){
            String[] input = br.readLine().split(" ");
            arr[i][0] = Integer.parseInt(input[0]);
            arr[i][1] = Integer.parseInt(input[1]);
            arr[i][2] = Integer.parseInt(input[2]);
        }

        int[][] dp = new int[N][3];
        dp[0][0] = arr[0][0];
        dp[0][1] = arr[0][1];
        dp[0][2] = arr[0][2];

        for(int i = 1; i < N; i++){
            dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + arr[i][0]; // 빨강으로 칠할 때
            dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + arr[i][1]; // 초록으로 칠할 때
            dp[i][2] = Math.min(dp[i - 1][0], dp[i - 1][1]) + arr[i][2]; // 파랑으로 칠할 때
        }

        int result = Math.min(Math.min(dp[N - 1][0], dp[N - 1][1]), dp[N - 1][2]);

        bw.write(result + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
}