이 문제는 DP 문제다.
왜냐하면 문제는 비용의 최솟값을 구하라고 하고 있는데
i 번째 순에서 최솟값을 특정할 수가 없기 때문이다. 뭔 말이냐면
5개 집이 존재 할 때 1 번째 → 2 번째 → 3번째 순으로 각 순서에서 현재까지 최소인 비용이라고 생각하고 색을 선택하면, 실제 5개의 집에 대한 최소 비용을 선택할 수 없다는 것이다.
R G B
1 2 3
4 2 3
3 1 3
R -> g or b (현재까지 보면, 2를 선택하는게 최소네~ -> G) -> 앞에서 G 를 선택했으니 R or B 중에 골라야함 -> B
그 결과 비용은 ( 1 , 2, 3 )
하지만 실제로는
R B G 를 선택하는게 최소임 (1,3,1)그러면, 결국은 뭔가 모든 경우를 해 봐야 할 것 같겠지만 → 이렇게 할 때면 “중복되는 경우의 수 “ 들이 존재하게 된다.
동적 계획법 문제를 풀 때면 “한 번 만 업데이트 하고, 캐싱 해서 쓰는 경우” 가 무엇인지를 생각 해야 한다고 생각한다..
이 문제에서는 i 번째 색이 c 이면서, 현재까지 비용이 w 인 경우에 대해서는 한 번으로 묶으면 될 것이라 생각했는데
그러면… 1000(집의 개수 ) x 3 ( 색의 종류 ) x 10000000( i 번째 집까지의 비용의 가지수 ) 가 되어버림..이 문제는 “비용” 까지는 생각 하는게 아닌가..????
아니면….
이전 집 색깔현재 비용
만 생각하면 되려나?
첫 번째 생각은 [i][c][w] 였고 두 번째 생각은 [c][w] 를 말하고 있는 거임. 이 근데 이것도 절대 안됨..사실상 i 번째가 꽤 중요하기 때문임.. 3 번째 집 선택할 때 까지 비용이 100이고 5 번째 집 선택할때 까지 비용이 100 이면, 3 번에서는 앞으로 또, 더 추가될 경우들이 더 많아서, c,w 만으로는 경우를 그룹화 시킬 수 없음.
아 근데 이렇게 하면 안되는 것 같다…
===========================
그냥 i 번째 집을 c 컬러로 선택한 경우 라고 하면..
- “cost[i][c] 는 i 번째를 c 컬러로 선택한 경우 i ~ end 까지의 최소 비용” 을 뜻하게 하면 괜찮을 것 같다. 결국 중복되는 경우는, i 부터 ~ end 까지의 경우들이 중복되는 것이기 때문이다.
