예전에 GP에서 풀어봤었던 House Robber 이라는 문제이다. 미국에 있었을때 DP 공부를 좀 했었는데 아마 가장 이해가 안됐었던 유형의 문제중 하나였을거같다. 다시 풀어봤을때도 사실 감이 하나도 안왔고 재귀 과정이 너무 헷갈렸어서 어지러웠지만 DP 유형의 문제들을 보고있자니 드는 공통적인 생각이 있다.
DP유형의 문제는 선택할거냐, 선택하지 않을거냐의 공통점이 있다. 혹은 1번의 방법과 2번의 방법이 있을때...로 시작하는 문제 타입에서도 쓰이는 기분이다. 그리고 대부분의 memorization 선택지에서 쓰이는 방법은 TOP-DOWN 방식인거 같고 이 문제또한 TOP-DOWN으로 시작하였다.
기본적인 룰은 서로 이웃인 집이 있을때 경찰이 올수있으므로 이웃을 피하는 조건이 있다. 처음에 혹시나 싶어서 2중 for 문으로 문제를 풀어볼려고는 했다만 i+1 의 해당집으로만 끝나는게 아니라 i+n 집을 털어야만 max값을 구할수도 있었기때문에 훨씬 더 많은 for룹이 필요하고 사고방식을 더 복잡하게 했어야했다. DP의 가장 좋은점은 매 순간마다 가장 최적의 값을 저장 할수있는 것인거 같다.
먼저 재귀 함수를 끝내는 조건문으로는 if(index >= nums.size()) 를 해주었다. 숫자가 끝나는 시점부터 이 집을 터는것이 이득일지, 혹은 이 집을 털지않고 다음집을 터는것이 이득인지를 memorization 테이블에 저장할수 있기 때문이다. 이런식으로 재귀 함수가 반복되고 끝나다보면 가장 최적의 값이 리턴이 된다. Memorization 테이블을 활용해주었기 때문에 여러번 반복되는 계산도 피할수있었고. 이 재귀 과정을 이해하는게 처음에는 많이 어려웠던거같다.
배운점:
1. 재귀를 이해하면 이해할수록 나중에 분명히 도움이 될것이다.
2. 선택을 하냐/안하냐 의 코드 구상을 잘 연습해야겠다.
