분명 예전에 풀었던건데,,, 왜 틀릴까!?!!?!? 악!
처음 풀었던 접근 방법에서 크게 벗어나진 않았지만,,, 아직 왜 틀렸는지 모르겠다. 알아보자!.
완전 처음에는 Recursive case에 for문을 넣었다. for i in range(4)를 해주고 dx[i]형태로 적어내려갔다.
근데 사실 이거 왜 틀렸는지 대충만 알겠다,,, 왜 틀렸을까?
뭐 대충 이런 코드였다,,,
5분만에 짠 후, 아이고~~ 잘짰네 백트래킹 이해 좀 했나~?싶었다.
왜 틀렸을까?? 생각해보자.
어,,, for문을 쓰면 왜 안되지?!?!?
-- 직접 손으로 해보았다,, --
for 문이 잘못된 것이 아니였다. 잘 보면 i == 3: 부분에서 int(param_data / data[cnt])를 안해주었다.
그리고 result_max부분도 0보다 더 작은 값이 최대일 수 있기 때문에 -int(1e9)로 했어야 했다...
반복문이 없는 것이 있는 코드보다 30ms나 더 빠르다. 왜인지 대충은 알겠지만 정확히 짚고 넘어가자.
for문과 없는 것의 차이를 알았다.
없는 것은 왜 가능하냐면,, 이 특성을 잘 이용한 것이다.
무슨 말이냐면, 어차피 모든 경우의 수를 구해줄 때는 그냥 되는대로 다 짚어서 깊은 탐색은 하면 되니 말이다.
쟤는 그냥 쭈욱 내려오면서 되는거 바로 재귀함수 호출하는데,
나는 for문으로 호출되지 않을 문장도 한번 더 거쳐가는 것이다.