백준 1149 RBG거리

haruponea·2021년 4월 4일
0

BOJ

목록 보기
35/41

문제 링크https://www.acmicpc.net/problem/1149

풀이
2차원 dp테이블을 사용하는 dp문제였습니다. dp[i][0]은 i번째 집을 빨강으로 칠할 때까지의 최솟값, dp[i][1]는 i번째 집을 초록으로 칠할 때까지의 최솟값, dp[i][2]는 i번째 집을 파랑으로 칠할때의 최솟값입니다. 점화식은 다음과 같습니다.
dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + R[i]
dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + G[i]
dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + B[i]

각각 이전 집을 다른 색으로 칠한 것의 최솟값에 현재 집의 색을 더해주면 됩니다.

Python

import sys
input = sys.stdin.readline
n = int(input())
R, G, B = [], [], []
dp = [[0]*3 for _ in range(n)]
for _ in range(n):
    r, g, b = list(map(int, input().split()))
    R.append(r)
    G.append(g)
    B.append(b)
dp[0][0] = R[0]
dp[0][1] = G[0]
dp[0][2] = B[0]
for i in range(1,n):
    dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + R[i]
    dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + G[i]
    dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + B[i]
print(min(dp[n-1][0], dp[n-1][1], dp[n-1][2]))

0개의 댓글