백준(BOJ) 17404 RGB거리 2(Python)

문제 내용

 

2차원 DP 문제.

처음 집에 색을 칠하는 경우 총 3개를 각각 나눠서 DP를 돌렸다.

그 이유는, 2번째부터 n-1번째 집까지는 i번째 집을 칠할 때 i-1번째와 다르게만 칠하면 되지만 n번째 집을 칠할 때에는 1번째 집을 칠한 색이 영향을 끼치기 때문이다.

그 외에는 크게 어려운 부분이 없는 DP 문제였다.

 

코드는 다음과 같다.

 

 

# -*- coding: utf-8 -*-
import sys
from collections import deque
import heapq
import copy
#input=sys.stdin.readline
#sys.setrecursionlimit(100000000)

n=int(input())
L=[]
for i in range(n):
    L.append(list(map(int,input().split())))
INF=10e9
ans=INF
for i in range(3):
    dp=[[INF,INF,INF] for i in range(n)]
    dp[0][i]=L[0][i]
    for j in range(1,n-1):
        k=min(dp[j-1][0],dp[j-1][1])
        if k!=INF:
            dp[j][2]=k+L[j][2]
        k=min(dp[j-1][1],dp[j-1][2])
        if k!=INF:
            dp[j][0]=k+L[j][0]
        k=min(dp[j-1][0],dp[j-1][2])
        if k!=INF:
            dp[j][1]=k+L[j][1]
    if i==0:
        ans=min(dp[j][0]+L[j+1][2],dp[j][1]+L[j+1][2],dp[j][0]+L[j+1][1],dp[j][2]+L[j+1][1],ans)
    elif i==1:
        ans=min(dp[j][0]+L[j+1][2],dp[j][1]+L[j+1][2],dp[j][1]+L[j+1][0],dp[j][2]+L[j+1][0],ans)
    else:
        ans=min(dp[j][1]+L[j+1][0],dp[j][2]+L[j+1][0],dp[j][0]+L[j+1][1],dp[j][2]+L[j+1][1],ans)
print(ans)

 

아이디어를 생각하는데 생각보다 시간이 좀 걸렸다.

금방 풀 수 있을 줄 알았는데,,,