다시 한번 풀어보는 Jump Game 문제이다. 사실 이 모든 문제들은 GP에서 한번씩 봤던 경험은 있었지만 전부 다 이해하지는 못했었고. 애초에 컴퓨터나 주변환경이 많이 다르기때문에 조용하게 집에서 큰 화면이랑 좋은 노래 들으면서 풀고있기 때문에 훨씬 더 집중이 잘되고 다시 풀고있지만 처음 푸는 기분이 든다.
이 전에 풀었던 Jump Game I 에서는 그저 마지막 index까지 가면 true를 리턴하면 됐지만 이번 문제 에서는 마지막 Index에 도달 하기까지 최소한의 점프를 리턴해야하는 문제이다. 되게 흥미로운 문제인데 다행히 조건중에 항상 마지막 index에 도달할수있다라고 명시되어서 다행이었다.
이 문제는 전에 풀었던 문제와 다르게 step 을 계속 follow 해줘야했다. 그저 도달할수 있다/없다가 아닌 얼마나 적게 갈수있냐를 계산해야 했기때문에 좀 애를 먹었던 문제이다.
내가 쓴 주석을 보면은 알겠지만 확실히 고민을 많이 했었다. 여기서 고민을 했었던거는 어떻게 min 값만을 저장하는 거였다. 그래서 처음에는
ret = min(1 + dfs(nums,index+i), dfs(nums,index+i))
같이 좀 괴상한 코드를 썼는데 이럴 필요가 전혀없었다. 애초에 minimum을 비교하면 됐었기에 처음에 만든 op1이라는 변수를 가장 큰 값으로 지정하고 만약에 마지막 index까지 갔다고 하면 0을 리턴해서 마지막 경로부터 +1 을 해주면서 op1의 값이랑 비교하면은 됐었다. 여기서 내가 또 실수했던거는 마지막 return phase 에서 그냥 return ret 이라고만 적었어서 op1의 값이 업데이트가 안됐었는데 이거는 내가 재귀에 과정을 많이 놓쳤었던거같다.
for 룹이 끝나고 재귀가 되는 과정에서도 추가적인 코드를 적었어야했고 그 답은 ret = op1 로 지정하는것이었다. 이렇게 되면 for 룹안에서 업데이트가 끝난 op1의 값을 이 전에 있었던 재귀 코드로 넘어갈수 있었기 때문에 결국에 op1의 값은 최소한의 스텝을 쭉 저장할수있었던것이다.
배운점:
1. ret 의 값을 항상 엄두하자.
2. 재귀 과정을 잘 따라가보자.
