이 문제 또한 GP 에서 처음 접했던 문제였고, 당시에 문제를 봤을때는 많이 혼란스러웠다. 이 전 DP 문제들을 풀면서도 아직 DP의 개념이 많이 헷갈리는 상태였는데 이 문제를 다시 보자니 또 어지러웠고 어떻게 해야할지 고민이 많이 갔었다.
하지만 문제를 천천히 다시 읽다보니 이 전에 풀었던 House Robber 문제와 되게 유사함을 느꼈고 접근을 하였다.
이 문제 또한 선택을 하냐/ 안하냐의 dfs 접근법이 필요했었다. 예를 들어, 숫자 하나를 선택했다면 그 숫자만큼의 점수를 얻고 선택한 숫자에 +1, -1의 숫자는 전부 사라진다. 그래서 사실상 다음 점수를 얻는거는 내가 선택한 숫자의 +2 만큼의 점수이다.
먼저 Frequency 를 얻기 위해서 unordered_map 을 써줬으면서 DFS를 접근했다. 여기서 내가 실수한 점이 뭐였냐면은 House Robber 문제처럼 index를 활용해 base case를 만들어야 하나 였다. 그러나 이 문제를 다시 한번 잘 읽어보면 이건 index로 접근할게 아니라 숫자 그 자체로 접근했어야 했던것이다. 만약 숫자를 선택하게 된다면 그것에 +2의 다음숫자를 찾아야만 했고 돌아오는 과정에서 숫자가 더 해지면됐기에 +2의 숫자가 map의 존재하는지를 확인하는게 중요했다.
그 케이스가 아니라면 계속 +1을 해줘서 숫자가 나올때까지만 확인하면 됐었다. 그러면은 Ret 안에는 결국 최대 점수만이 나오게 되기때문이다. House Robber 문제와 정말 유사하고 int op1, op2 라는 다른 계산을 넣어서 마지막에 max값을 해준것도 중요하게 배울점이라고 생각한다.
그러나 사실 이걸 보면서도 이해가 될때도 있고 안될때도 있는거보면 아직도 갈길은 먼거같다. 재귀 과정을 머리속에서 잘 따라가는 연습이 계속 필요할거같다.
배운점:
1. Select/ Not Select 의 선택지에 따른 DFS방법
2. 최대 값을 얻기 위해 ret 값을 어떻게 설정해야하는지
