rapaeljin   6년 전

사실  N이 10000만 되도 시스템이 뻗어버리더라고요...

L 딕셔너리도 확인해 보았는데 함숫값들은 잘 저장이 되는데

왜 시간이 단축되지 않는지 잘 모르겠습니다ㅠㅠ

혹시 N 이하의 모든 수에 대해 결과를 다 저장할 필요가 없어서인가요? 

다른 알고리즘이 필요하다면 소정의 힌트 부탁드려요 :3

jh05013   6년 전

재귀가 너무 깊이 들어갑니다. setrecursionlimit을 하더라도 재귀로 인해 메모리 한도를 초과하게 됩니다.

rapaeljin   6년 전

재귀 호출 횟수는 dp를 쓰는지 안쓰는지와는 상관이 없나요?

rapaeljin   6년 전

재귀를 안쓰니 바로 풀려버렸습니다 감사합니다!

jh05013   6년 전

횟수가 아니라 깊이의 문제입니다.

N = 100만을 넣어 보면 Least(N-1) 때문에 Least(1000000) -> Least(999999) -> Least(999998) -> ... -> Least(500000)까지 재귀가 들어가야 하므로 재귀의 깊이는 약 50만까지 갈 수 있습니다. Least(500000)은 N//2에서 이미 계산되었으므로 여기에서 멈추지만, 그 사이의 값은 N//3이나 N//2로 만들 수 없는 값이기 때문에 N-1을 반복해서 들어갈 수밖에 없습니다.

댓글을 작성하려면 로그인해야 합니다.