[백준/Java] 1149 - RGB 거리

승래·2026년 1월 3일

DP 백준 자바

1149 - RGB 거리

문제 바로가기

문제

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

1번 집의 색은 2번 집의 색과 같지 않아야 한다.
N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

입력

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

요구사항

목표: $N$ 개의 집을 빨강(R), 초록(G), 파랑(B) 중 하나의 색으로 칠하는 비용이 주어졌을 때, 모든 집을 칠하는 비용의 최솟값을 구해야 한다.
제약 조건 (규칙):
- 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
- $N$ 번 집의 색은 $N-1$ 번 집의 색과 같지 않아야 한다.
- $i$ ( $2 \le i \le N-1$ )번 집의 색은 $i-1$ 번, $i+1$ 번 집의 색과 같지 않아야 한다.
- 즉, 인접한 집끼리는 같은 색을 칠할 수 없다.
입력: 집의 수 $N$ ( $2 \le N \le 1,000$ ), 각 집을 R, G, B로 칠하는 비용.

접근 방식

이 문제는 전형적인 다이나믹 프로그래밍(DP) 문제다.
모든 경우의 수를 탐색하면 $3^N$ 이 되어 시간 초과가 발생하므로, 이전 단계까지의 최솟값을 누적하여 현재의 최적해를 구해야 한다.

1) 점화식 도출

현재 집( $i$ )을 특정 색으로 칠할 때의 최소 비용은 "현재 비용 + 이전 집( $i-1$ )을 다른 색으로 칠했을 때의 최소 누적 비용"이다.

$i$ 번 집을 빨강(0)으로 칠하려면? $\rightarrow$ $i-1$ 번 집은 초록(1) 또는 파랑(2)이어야 함.
$i$ 번 집을 초록(1)으로 칠하려면? $\rightarrow$ $i-1$ 번 집은 빨강(0) 또는 파랑(2)이어야 함.
$i$ 번 집을 파랑(2)으로 칠하려면? $\rightarrow$ $i-1$ 번 집은 빨강(0) 또는 초록(1)이어야 함.

2) 나머지 연산(Modulo)을 활용한 코드 단축

보통은 if-else나 switch문으로 색깔 3가지를 각각 하드코딩하지만, 색상 인덱스가 0, 1, 2로 순환한다는 점을 이용하면 코드를 획기적으로 줄일 수 있다.

현재 색이 j일 때, 칠할 수 있는 이전 집의 색은 (j+1)%3과 (j+2)%3이 된다.
점화식:
$dp[i][j] = cost + \min(dp[i-1][(j+1)\%3], \ dp[i-1][(j+2)\%3])$

3) 메모리 최적화

입력값을 저장하는 arr 배열과 계산값을 저장하는 dp 배열을 따로 만들 필요가 없다. 입력을 받음과 동시에 이전 dp 값을 참조하여 계산하면 배열 하나(N x 3)로 충분하다.

코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());

        int[][] dp = new int[n][3];

        for(int i=0; i<n; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<3; j++) {
                int cost = Integer.parseInt(st.nextToken());

                if(i==0) {
                    dp[i][j] = cost;
                }
                else {
                    dp[i][j] = Math.min(cost + dp[i-1][(j+1) % 3], cost + dp[i-1][(j+2) % 3]);
                }
            }
        }

        int answer = Integer.MAX_VALUE;
        for(int cost : dp[n-1]) {
            answer = Math.min(answer, cost);
        }
        System.out.println(answer);
    }
}

느낀점

메모리 낭비 줄이기: 처음에는 막연하게 int[N][N] 크기의 배열을 생각했는데, 생각해보니 색상은 3가지로 고정되어 있었다. 불필요한 메모리를 잡지 않도록 int[N][3]으로 선언하는 것이 효율적임을 깨달았다.
하드코딩 탈피: 처음엔 switch문을 써서 case 0, case 1, case 2를 일일이 작성했었다. 하지만 (j+1)%3과 (j+2)%3을 이용해 인덱스를 순환시키니 코드가 훨씬 간결해졌다. 알고리즘 문제에서 나머지 연산이 인덱스 처리에 얼마나 유용한지 체감했다.
DP의 핵심: "지금 내가 빨간색을 칠하려면, 앞집은 무조건 초록 아니면 파랑 중 더 싼 걸 골라야 해"라는 단순한 논리를 배열에 누적해가는 과정이 DP의 핵심임을 이해했다.