[백준 1149] DP 동적계획법2

이전 글에서 DP에 대해 이제 감이 잡히는 것 같다고 했는데 전혀 아니었나보다.

무조건 스스로 풀겠다 다짐해놓고 결국 또 구글링했다. 문제들을 다 구글링으로 풀어서 실력이 과연 늘지 의문이다.

 

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

dp = [[0]*3 for _ in range(n)]
dp[0] = cost[0]

for i in range(1,n):
    dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + cost[i][0]
    dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + cost[i][1]
    dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + cost[i][2]
print(min(dp[n-1]))

98% 베낀 코드다. 

이중 for문으로 첫번째 집부터 방문하는 것만 생각했는데, 생각의 폭이 좁았다.

1. 첫번째 집의 가격을 고정시키고

2. 두번째 집부터 방문하면서, 이전 집의 3가지 가격 중 가장 작은 것을 선택하고 현재 집의 가격을 각각 더한다.

3. 그렇게 마지막 집까지 방문하면

이전 집과 중복되지 않으면서 최소값만 골라 더할 수 있게 된다.

 

 

이 문제는 나중에 꼭 다시 풀어봐야겠다.

DP문제 중 쉬운 편인 것 같은데 아직 공부한지 얼마 안 됐으니 괜찮다고 위로를 해보며 오늘은 여기서 만족하기로 했다.