N = 100만을 넣어 보면 Least(N-1) 때문에 Least(1000000) -> Least(999999) -> Least(999998) -> ... -> Least(500000)까지 재귀가 들어가야 하므로 재귀의 깊이는 약 50만까지 갈 수 있습니다. Least(500000)은 N//2에서 이미 계산되었으므로 여기에서 멈추지만, 그 사이의 값은 N//3이나 N//2로 만들 수 없는 값이기 때문에 N-1을 반복해서 들어갈 수밖에 없습니다.
rapaeljin 6년 전
사실 N이 10000만 되도 시스템이 뻗어버리더라고요...
L 딕셔너리도 확인해 보았는데 함숫값들은 잘 저장이 되는데
왜 시간이 단축되지 않는지 잘 모르겠습니다ㅠㅠ
혹시 N 이하의 모든 수에 대해 결과를 다 저장할 필요가 없어서인가요?
다른 알고리즘이 필요하다면 소정의 힌트 부탁드려요 :3