백준 1149번: RGB거리

 

RGB 거리 문제 풀이: 동적 계획법(DP) 활용

이 문제는 N개의 집을 주어진 비용으로 칠하는 문제로, 각 집을 세 가지 색 중 하나로 칠할 수 있습니다. 다만, 두 집이 인접해 있을 경우, 두 집의 색이 같지 않도록 해야 하므로, 이를 해결하기 위해 동적 계획법(DP)을 사용합니다.

문제 분석

• 각 집을 빨간색, 초록색, 파란색 중 하나로 칠할 수 있으며, 각 색에 대한 비용이 다릅니다.
• N개의 집을 칠할 때, 인접한 두 집은 다른 색으로 칠해야 하므로, 최소 비용을 구하는 것이 목표입니다.

해결 방법

1. 문제의 상태 정의:
   • score[i][j]: i번째 집을 j색으로 칠하는 비용을 나타냅니다.
   • dp[i][j]: i번째 집까지 칠할 때, j색으로 칠한 최소 비용을 기록합니다.
2. 점화식:
   • dp[i][0] (i번째 집을 빨간색으로 칠하는 비용)은 이전 집을 초록색 또는 파란색으로 칠한 최소 비용에 현재 집의 빨간색 비용을 더한 값입니다.
   • 비슷하게 dp[i][1], dp[i][2]를 계산합니다.
3. 최종 결과:
   • 마지막 집을 칠할 때, 빨간색, 초록색, 파란색을 칠할 수 있으므로 세 가지 경우 중 최소값을 선택하면 됩니다.

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

public class Main {

    public static void main(String args[]) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        int score[][] = new int[N + 1][3];
        int dp[][] = new int[N + 1][3];

        // 각 집을 칠하는 비용을 입력받습니다.
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            score[i][0] = Integer.parseInt(st.nextToken());  // 빨간색 칠하는 비용
            score[i][1] = Integer.parseInt(st.nextToken());  // 초록색 칠하는 비용
            score[i][2] = Integer.parseInt(st.nextToken());  // 파란색 칠하는 비용
        }

        // 첫 번째 집은 비용이 그 집의 색에 맞게 초기화됩니다.
        dp[0][0] = score[0][0];
        dp[0][1] = score[0][1];
        dp[0][2] = score[0][2];

        // 두 번째 집부터는 이전 집을 칠한 색에 따른 최소 비용을 구합니다.
        for (int i = 1; i < N; i++) {
            dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + score[i][0];
            dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + score[i][1];
            dp[i][2] = Math.min(dp[i - 1][0], dp[i - 1][1]) + score[i][2];
        }

        // 마지막 집을 칠할 때, 세 가지 색 중 최소 비용을 출력합니다.
        System.out.println(Math.min(Math.min(dp[N - 1][0], dp[N - 1][1]), dp[N - 1][2]));
    }
}

 

시간 복잡도

• 입력받은 집의 수 N에 대해 DP 배열을 갱신하는데 O(N) 시간이 걸립니다. 따라서 전체 시간 복잡도는 O(N)입니다.