문제
풀이
DP... 정말 너무 어렵다 일단 점화식을 짰는데 이 경우는 인접한 집의 색상이 같으면 안된다
3
26 40 83
49 60 57
13 89 99
인경우 3개의 집인데 만약 첫번째 집의 색상이 빨간색이라면 선택할 수 있는 다음 집의 색상의 수는 2개 그리고 다음 집의 선택할수 있는 색상의 개수도 근접한 색상과 같으면 안된다
dp[현재 집][색상] 으로 2차 배열로 잡고 정하면 해당 값으로는
[n번째 집]까지 [색상] 을 지정할때 가장 작은 값이 설정될 것이다.
0번째 색을 선택한 경우
dp[i][0] = rgb[i][0] + Math.min(dp[i - 1][1], dp[i - 1][2])
Math.min(dp[i - 1][1], dp[i - 1][2]) 는 이전 색까지 1,2번째 색을 선택한경우에서 가장 작은 값을 설정해주는 것 이다.
이부분을 구하기가 제일 어려웠다
막상 2차 배열로 구현을 해놨는데, 이전값까지는 어떻게 작은 값을 불러오면 될까?
에서 딱 막혀버리더라ㅜ...ㅠㅠ허접....이다...
전체 코드
Reference
develop life