> For the complete documentation index, see [llms.txt](https://heunnajo.gitbook.io/algorithms-problem-solving-skills/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://heunnajo.gitbook.io/algorithms-problem-solving-skills/dynamic-programming/rgb-street.md).

# 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 중 최솟값**은 다르다.