RGB Street

내 접근 방법 : 1차원 DP

d[n] = n개의 집 색칠 최소 비용 => n번째 집 색이 0인지, 1인지, 2인지에 따라 최솟값을 구하면 정답이 된다! d[n] = Math.min(d[n-1]+P[0] , d[n-1]+P[1] , d[n-1]+P[2])

정답 찾는 접근 방법은 맞았다! 그런데 정답에는 2차원 DP를 정의해서 n번째 집의 색을 함께 기록해주었다! d[n] = Math.min(d[n][0], d[n][1], d[n][2]) d[n][0] = Math.min(d[n-1][1],d[n-1][2]) + P[n][0] d[n][1] = Math.min(d[n-1][0],d[n-1][2]) + P[n][1] d[n][2] = Math.min(d[n-1][0],d[n-1][1]) + P[n][2]

여기서 d[n-1]이라고 단순히 계산했는데, 사실 n번째 집 색이 0 이라면 n-1은 1 또는 2 중 최솟값이 된다!!! 마찬가지로 n=1 ) n-1 = 0 또는 2 중 최솟값 마찬가지로 n=2 ) n-1 = 0 또는 1 중 최솟값

n-1과 n-1 = 0 또는 1 중 최솟값은 다르다.