백준 1149번 - RGB 거리

RGB 거리 문제 바로 가기

풀이 날짜: 2026-01-11

baekjoon 알고리즘 문제 풀이

풀이 코드


import sys
input = sys.stdin.readline

n = int(input())
color = [list(map(int, input().split())) for _ in range(n)]

dp = [[0]*3 for _ in range(n)]
dp[0] = color[0]

for i in range(1, n):
    dp[i][0] = color[i][0] + min(dp[i-1][1], dp[i-1][2])
    dp[i][1] = color[i][1] + min(dp[i-1][0], dp[i-1][2])
    dp[i][2] = color[i][2] + min(dp[i-1][0], dp[i-1][1])
print(min(dp[n-1]))

문제 이해의 어려

RGB 거리 문제를 처음 봤을 때, 가장 헷갈렸던 점은 “집이 여러 개 있고, 색도 3개나 되는데 이걸 어떻게 관리하지?”라는 생각이었다. 특히 각 집마다 비용이 다르고, 앞집과 같은 색을 쓰면 안 된다는 조건 때문에 단순히 가장 싼 색을 고르는 방식(그리디)이 아니라는 점에서 혼란이 컸다.

이 문제는 앞에서 어떤 선택을 했는지가 뒤 선택에 영향을 주는 구조였고, 이 시점에서 “아, 이건 DP구나”라는 감이 왔다.

왜 그리디로 풀 수 없는 문제인가

처음에는 “각 집에서 가장 싼 색을 고르면 되지 않나?” 라는 생각이 들었지만, 곧 문제가 있다는 걸 깨달았다.

앞 집에서 가장 싼 색을 골라버리면, 다음 집에서 선택 가능한 색이 제한되고 결과적으로 전체 비용이 더 커질 수 있다.

즉, 현재의 최선 선택이 전체 최적해를 보장하지 않는다.
이런 구조는 전형적인 동적 계획법(DP) 문제의 특징이다.

DP 정의

i번째 집을 j색(R/G/B)으로 칠했을 때, 0번 집부터 i번 집까지의 최소 비용

예를 들어, i번째 집을 빨강(0)으로 칠한다고 가정하면:

i-1)번째 집은 초록(1) 또는 파랑(2)만 가능
따라서 점화식은 dp[i][0] = color[i][0] + min(dp[i-1][1], dp[i-1][2]) 이렇게 구성이 된다.
즉, 핵심은 현재 색을 제외한 이전 집의 두 색 중 최소값을 더하는 것이다.

헷갈렸던 점 정리

dp[0] = color[0] 을 왜 설정하는가

이 부분은 DP에서 가장 중요한 기저 조건이다.

첫 번째 집은:

이전 집이 없고
색 제한도 없기 때문에

각 색을 선택했을 때의 최소 비용은 그냥 자기 자신의 비용이 된다.

Vienna sausage