[백준] RGB거리 (1149번)

문제 흐름

1. 문제 목표:
   • 각 집을 세 가지 색(빨강, 초록, 파랑) 중 하나로 칠합니다.
   • 단, 인접한 두 집은 같은 색으로 칠할 수 없습니다.
   • 모든 집을 칠할 때의 최소 비용을 구해야 합니다.
2. 입력 설명:
   • 첫 줄에 집의 개수 n이 주어집니다.
   • 이후 n개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠할 때 드는 비용이 주어집니다.
3. 제약 조건:
   • DP(동적 계획법)을 사용해 인접 집의 색이 겹치지 않도록 최소 비용을 누적합니다.

 

핵심 아이디어

• DP(동적 계획법)으로 최소 비용을 누적 계산합니다.
• 각 집을 특정 색으로 칠할 때 최소 비용은 이전 집에서 자신과 다른 색을 선택한 최소 비용과 현재 색의 비용을 더한 값입니다.
• 마지막 집까지 누적된 비용 중 최소값을 결과로 출력합니다.

 

알고리즘 흐름

1. 입력받기:
   • n개의 집과 각 색의 비용을 2차원 배열에 저장합니다.
2. DP 테이블 갱신:
   • 두 번째 집부터 마지막 집까지 각 색을 칠할 때의 누적 최소 비용을 계산합니다.
   • 현재 집을 i, 색을 j로 칠할 때, 이전 집에서 j와 다른 색의 최소 비용을 누적합니다.
     (예: 현재 집을 빨강으로 칠할 때, 이전 집은 초록 또는 파랑이어야 함.)
3. 최종 최소 비용:
   • 마지막 집까지 칠한 후, 마지막 집의 세 가지 색 중 최소값을 출력합니다.

 

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);


        // 집의 개수와 결과 변수
        int result = Integer.MAX_VALUE;
        // 집의 개수 입력
        int n = in.nextInt();
        in.nextLine();

        // 집을 칠하는 비용 입력 (n x 3 배열)
        int[][] colors = new int[n][3];

        for (int i = 0; i < n; i++) {
            String[] arr = in.nextLine().split(" ");
            for (int j = 0; j < 3; j++) {
                // 각 집의 색깔별 비용 저장
                colors[i][j] = Integer.parseInt(arr[j]);
            }
        }

        // 두 번째 집부터 마지막 집까지 최소 비용 계산
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < 3; j++) {
                // 현재 색을 j로 칠할 때, 이전 집에서 j가 아닌 색 중 최소 비용 찾기
                int min = Integer.MAX_VALUE;
                for (int k = 0; k < 3; k++) {
                    if (j != k) { // 같은 색이 아니어야 함
                        min = Math.min(colors[i - 1][k], min);
                    }
                }
                // 현재 색 비용에 이전 집의 최소 비용 누적
                colors[i][j] += min;
            }
        }

        // 마지막 집의 세 색깔 중 최소 비용 찾기
        for (int i = 0; i < 3; i++) {
            result = Math.min(result, colors[n - 1][i]);
        }

        // 최소 비용 출력
        System.out.println(result);
    }
}