BOJ-1149 RGB거리

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

문제 소개

1번부터 N번 집이 순서대로 있고, 연속된 집을 같은 색으로 칠하지 않으면서 비용을 최소로 하는 문제이다.

문제 풀이

DP로 간단하게 풀이하였다. 리스트 dp로 메모이제이션을 사용했다.

dp[i][0], dp[i][1], dp[i][2]은 각각 1번 집부터 i + 1번 집까지 칠했을 때 빨강, 초록, 파랑으로 색칠을 마무리했을 때의 비용을 의미한다.

1번집의 비용 정보만 dp에 입력하여 초기화한 후, 반복문을 통해 최소 비용을 찾아가며 dp에 값을 저장한다.

min(dp(n - 1))은 N번까지 색칠을 완료했을 때 비용의 최솟값을 의미한다.

코드

import sys
input = lambda: sys.stdin.readline().rstrip()

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

dp = [[0] * 3 for _ in range(n)]
dp[0] = arr[0].copy()       # 1번 집의 값으로 첫 인덱스 초기화

for i in range(1, n):       # 반복문을 통해 dp값 업데이트
    dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + arr[i][0]
    dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + arr[i][1]
    dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + arr[i][2]
print(min(dp[n - 1]))