백준 1149 RGB 거리 JAVA 풀이 (DP, 누적 최소값, 시간복잡도)

🔗 문제 링크

https://www.acmicpc.net/problem/1149

---

📌 문제 개요

백준 1149번 RGB 거리는 각 집을 빨강, 초록, 파랑 중 하나로 칠할 때
인접한 집은 같은 색을 사용할 수 없다는 조건에서 전체 비용의 최솟값을 구하는 문제입니다.

 

---

📌 접근 방법

이 문제는 대표적인 DP 기초 문제입니다.

각 집마다 3가지 선택지가 있으므로 이전 상태를 기반으로 누적해 나가면 됩니다.

 

DP 정의 : dp[i][color] = i 번째 집까지 고려했을 때 최소 비용

 

---

📌 핵심 아이디어

현재 집을 특정 색으로 칠하려면
이전 집은 다른 색이어야 합니다.

---

📌 점화식

dp[i][0] = Math.min(dp[i-1][1], dp[i-1][2]) + cost[i][0];
dp[i][1] = Math.min(dp[i-1][0], dp[i-1][2]) + cost[i][1];
dp[i][2] = Math.min(dp[i-1][0], dp[i-1][1]) + cost[i][2];

 

즉, "현재 색 ≠ 이전 색" 조건만 지키면 된다

---

📌 처리 흐름

입력
→ cost 배열 저장
→ dp[0] 초기화
→ i = 1 ~ N-1 반복
→ 각 색마다 이전 두 색 중 최소 선택
→ 마지막 집에서 최소값 출력

 

---

📌 전체 코드

import java.io.*;
import java.util.*;

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

        int N = Integer.parseInt(br.readLine());
        int[][] cost = new int[N][3];
        int[][] dp = new int[N][3];

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            cost[i][0] = Integer.parseInt(st.nextToken());
            cost[i][1] = Integer.parseInt(st.nextToken());
            cost[i][2] = Integer.parseInt(st.nextToken());
        }

        // 초기값
        dp[0][0] = cost[0][0];
        dp[0][1] = cost[0][1];
        dp[0][2] = cost[0][2];

        for (int i = 1; i < N; i++) {
            dp[i][0] = Math.min(dp[i-1][1], dp[i-1][2]) + cost[i][0];
            dp[i][1] = Math.min(dp[i-1][0], dp[i-1][2]) + cost[i][1];
            dp[i][2] = Math.min(dp[i-1][0], dp[i-1][1]) + cost[i][2];
        }

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

        System.out.println(result);
    }
}

 

---

📄 정리

이 문제는 DP의 기본 패턴을 익히기에 매우 좋은 문제입니다.

• 상태 정의
• 이전 상태 활용
• 조건(같은 색 금지) 반영