baechu259   1년 전

몇몇 블로그 글 읽어보니까 점화식으로 푸는 것 같아서 비슷하게 따라해보려고 했는데 메모리초과가 나옵니다.

더 효율적으로 진행해야 한다는 건 알겠는데, 어느 부분이 메모리초과인지 잘 모르겠습니다.

pls에 죄다 append 하는 게 오래 걸리는 작업인가요?

나름 set이 연산이 빠를 거라고 생각해서 넣은 건데 부족한 걸까요?

답변 기다리겠습니다! 감사합니다.

hych0502   1년 전

이 사이트에 잘 정리되어있는 것 같습니다. set이 생각보다 메모리를 많이 잡아먹네요

https://github.com/BecomeWease...

n이 999998일 경우에 메모리가 134217944로 메모리 초과가 발생하는 것 같습니다.

bamgoesn   1년 전

위 코드는 set의 연산이 느려서 문제가 되는 건 아닙니다.

첫째로 pls의 크기가 너무 커질 수 있습니다. n이 커짐에 따라 탐색한 수가 점점 늘어나서 메모리를 너무 많이 차지합니다. n+=1 이후 n의 값이 25가 되는 시점에서 arr의 길이가 1억을 넘어갑니다. 이 길이는 특히 크기가 2~3배씩 증가하는데 입력이 933119일 때 정답이 30이거든요. 그러면 set의 크기가 수백억이 될 테니까 메모리 안에 다 들어갈 수가 없겠죠.

이 문제는 pls에 들어갈 값을 최대 1000000으로 제한하면 해결됩니다. 지금 코드는 pls에 들어가는 값이 얼마나 크든지 상관 없이 pls에 무조건 넣고 있는데, 이 값을 제한하면 한번에 pls 안에 들어가는 수의 개수가 많이봐야 1000000개겠죠.

둘째로 arr는 리스트인데 a가 arr 안에 있는지 없는지를 in 문법을 사용하고 있다는 게 문제입니다. arr의 길이가 $N$일 때 in 문법으로 값이 있는지 없는지를 판단하는 건 시간복잡도가 $O(N)$입니다. 이 때문에 $N$이 커지면 코드가 비효율적이게 됩니다.

이는 pls를 비우는 시점을 조금 고쳐서, while a not in pls로 코드를 고치면 해결됩니다. set 안에 값이 있는지 없는지는 $O(1)$ 안에 계산되기 때문입니다.

하지만 이렇게 해도 높은 확률로 시간초과를 받을 겁니다. 이는 같은 수를 여러 번 보지 않겠다는 DP의 핵심을 간과했기 때문인데요, 지금 코드는 pls에 수를 넣을 때 이 수가 이미 한 번 본 수인지 아닌지를 따지지 않고 있습니다. 따라서 어떤 수에 도달하기 위한 방법이 여러 가지가 있으면, 각각의 길이에 대해서 pls에 매번 집어넣게 됩니다.

이미 도달하는 최소의 방법을 계산한 수는 다시 안 봐도 되므로, 이 부분도 한번 고쳐보세요. 그러면 set을 사용하더라도 통과될 겁니다.

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