[백준][DP] 17404.RGB거리 2

17404.RGB거리 2

 

 

• 내 풀이
  • 2차원 DP 
  • 첫번째 집을 R,G,B 각각을 선택했을 경우를 다 돌아봐야함
    • j에만 값을 넣어두면 나머지 집들은 INF라 최솟값 j를 선택하게 됨
  • 앞집과 겹치지 않게 선택
    • answer은 dp[n]중에 j가 아닌 값만 확인해서 최솟값 넣어주기

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

answer=float('inf')
for j in range(3):
    dp = [[float('inf') for j in range(3)] for i in range(n + 1)]
    dp[1][j]=house[1][j]
    for i in range(2,n+1):
        dp[i][0]=house[i][0]+min(dp[i-1][1], dp[i-1][2])
        dp[i][1]=house[i][1]+min(dp[i-1][0], dp[i-1][2])
        dp[i][2]=house[i][2]+min(dp[i-1][0], dp[i-1][1])

    answer=min(answer,dp[n][(j+1)%3], dp[n][(j+2)%3])

print(answer)