Python - [백준]1149-RGB거리

출처

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

문제

왼쪽 집과 겹치지 않는 색깔로 칠하되 비용을 최소로 구하는 문제이다.

접근 방법

문제 조건을 잘 살펴보면, 2번째 집부터 N번째의 집 까지, 왼쪽 집과 색깔을 겹치지 않게 고르면 되는 문제이다.

DP에 기록을 하기 위해 점화식을 먼저 구한다.

• 내 집에 BLUE를 칠하는 경우, 그 색을 제외한 앞 집의 RED와 GREEN 중 비용이 최소인것을 구하면 된다.

다른 두개의 색깔에 대해서도 같은 과정을 수행하여 모두 기록하면 된다.

풀이

점화식을 dp[i][j] = min(dp[i-1][(j+1)%3], dp[i-1][(j+2)%3]) + arr[i][j] 로 구성하여 DP배열에 최소값을 기록해두었다.

import sys
input = sys.stdin.readline

n = int(input())
arr = [list(map(int, input().split())) for i in range(n)]
dp = [[1001]*3 for i in range(n)]
dp[0] = arr[0]

for i in range(1, n):
    for j in range(3): #DP배열 세번 기록하기 위함
        dp[i][j] = min(dp[i-1][(j+1)%3], dp[i-1][(j+2)%3]) + arr[i][j]
            
print(min(dp[n-1]))