백준 1149번 RGB거리

문제링크

이 문제는 이해하는데까지 정말 오래걸렸다😫 이해하고나니 정말 체한것 다 내려간 기분..
전형적인 동적계획법(DP)문제인데, 어려운 개념같지만 문제만 이해하면 코드짜는데는 그렇게 어렵지않다.

문제이해

예제를 보며 문제를 간단하게 이해해보면 3개의 집을 빨간색, 파란색, 초록색으로 칠하는데 이웃한 집은 같은 색으로 칠 할 수없다. [0]라인부터 [1], [2]까지 미니멈 가격을 DP 리스트에 추가해준다.
[1][0]은 빨강이니까 [0][1]인 G(40)과 [0][2]인 B(83)을 더한 값 중 더 작은 값을 DP의 [1][0]자리에 넣는다.
for문을 돌리며 첫번째 for문에선 [1]라인이 i, [0]라인이 i-1, 두번째 for문에선 [2]라인이 i, [1]라인이 i-1
아래의 코드를 보면 아마 이해가 더 쉬울것이다.

코드

n = int(input())
dp = [[0]*3 for _ in range(n)]
#0으로 리셋되어있는 리스트 생성
#현재 [0,0,0], [0,0,0], [0,0,0]인 상황
house = []
#house리스트에 input받은 값 넣어 줄것임
for _ in range(n):
    house.append(list((map(int, input().split()))))
dp[0] = house[0] #dp 첫 라인은 house 첫 라인으로 픽스

for i in range(1,n): #index[1]부터니까 range1부터
#dp 두,세번째 라인 채우기
    dp[i][0] = min(dp[i-1][1],dp[i-1][2]) + house[i][0]
    dp[i][1] = min(dp[i-1][0],dp[i-1][2]) + house[i][1]
    dp[i][2] = min(dp[i-1][0],dp[i-1][1]) + house[i][2]
print(min(dp[n-1]))

이해를위해 첨부한 두개의 리스트 dp와 house

print(dp)
print(house)

-> [[26, 40, 83], [89, 86, 83], [96, 172, 185]]
-> [[26, 40, 83], [49, 60, 57], [13, 89, 99]]

뭔가 다 이해했다고 생각했는데 말로 설명하려니 잘 안된다😂
갈길이 정말 멀다ㅎㅎ 즐겁다ㅎㅎㅎㅎ!!!!!