[백준-파이썬] 1149 : RGB 거리

문제로 가기

접근 🌰🍂

DP로 풀었다. 어떤 색으로 집을 칠할지, 몇 번째 집인지를 담은 2차원 리스트를 만들었다.

1번 집은 그냥 칠하면 된다. 그 이후 집들은 그 이전 집 색깔과 겹치지 않게 최소 비용으로 칠했다. 예를 들어, 현재 집을 빨강으로 칠할 때의 최소 비용을 구해야 하는 경우를 생각해보자. 그 이전 집이 초록일 때, 파랑일 때 최소 비용 중 싼 것을 택하고, 현재 집을 빨강으로 칠하는 비용을 더해서 dp 테이블을 채웠다.

코드 👩‍💻

import sys

input = sys.stdin.readline

N = int(input())
house_color_costs = list(list(map(int, input().split())) for _ in range(N))

dp = [[0] * 3 for _ in range(N)] # 각 집이 각 색깔(빨, 초, 파)로 칠해졌을 때의 최소 비용
# 첫번째 집 칠할 때
dp[0][0], dp[0][1], dp[0][2] = house_color_costs[0][0], house_color_costs[0][1], house_color_costs[0][2]

# 두번째 집부터
for i in range(1, N):
    dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + house_color_costs[i][0]
    dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + house_color_costs[i][1]
    dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + house_color_costs[i][2]

# 정답
print(min(dp[N-1][0], dp[N-1][1], dp[N-1][2]))