[백준] [DP] 1149. RGB 거리

1149. RGB 거리

• 내 풀이 : 중복순열 - 시간초과 error
  • 테스트케이스 전부 통과

#1~n 
# 1 != 2 색깔
# n-2 != n
# 2~n-1 앞뒤로 달라야함 
# 모든 집을 칠하는 비용 최솟값
from itertools import product as p

#빨강 초록 파랑
n=int(input())
house=[]
for i in range(n):
    house.append(list(map(int,input().split())))

#중복순열인데 앞과달라야함
answer=1e9
for pro in p((0,1,2), repeat=n):
    result=0
  
    for idx,p in enumerate(pro):
        if idx>0:
            if pro[idx-1]== pro[idx]:
                break
        result+=house[idx][p]
    else: #break 안된경우
        answer=min(answer, result)

print(answer)

 

• DP
  • 0, 1, 2 : 빨강, 초록, 파랑
  • i번째 위치에서 각 색깔을 칠했을 때의 최소비용 매번 갱신

n=int(input())
house=[]
for i in range(n):
    house.append(list(map(int,input().split())))

#DP 풀이
#0,1,2 :빨강 초록 파랑
#i번째집을 각 색깔로 칠했을 때의 최소비용 
for i in range(1, n):
    house[i][0] = min(house[i - 1][1], house[i - 1][2]) + house[i][0]
    house[i][1] = min(house[i - 1][0], house[i - 1][2]) + house[i][1]
    house[i][2] = min(house[i - 1][0], house[i - 1][1]) + house[i][2]

print(min(house[n - 1][0], house[n - 1][1], house[n - 1][2]))