celeste13   7년 전

실행하면 런타임에러가 뜨네요

이클립스에서 실행하면 잘됩니다

왜그런지 아시는분 계실까요..

devetude   7년 전

위와 같이 재귀 함수 형태로 해당 문제를 푸실경우 계속해서 heap 영역에 호출된 함수가 올라가기 때문에(return을 만나기 전까지는)

조금만 숫자가 큰 n과 r을 만나면 바로 힙 오버플로가 발생하여 런타임 에러가 발생합니다.


더군다나 이항계수를 위와 같이 푸시면 왠만한 문제는 TLE(시간초과)를 경험하실겁니다.

분할정복법을 사용하는 경우 위와같이 재귀 함수는 이미 계산이 끝난 이항계수를 또 계산하고 또 계산하고 수십번에서 수백번 계산한 것을 또 계산하면서 불필요한 처리를 하는 것이지요. 그래서 보통 동적계획법(다이나믹 프로그래밍)을 이용하여 메모이제이션 즉, cache[n + 1][r + 1] 배열을 사용해서 이미 계산한 결과를 저장해두고 캐시에 있는 결과(즉 이미 계산한 이항계수의 경우 또다시 재귀 메소드를 호출하지 않도록)를 사용하도록 코드를 짭니다...


더군다나 이 문제는 동적계획법으로도 풀 수 없습니다. 이유는 충분한 메모리가 없기때문에 문제의 최대 조건인 20억인 경우 메모이제이션을 하려 할 경우 공간복잡도가 매우 크기 때문에 또한 힙 오버플로를 경험하시게 됩니다.


따라서 이 문제는 직접 nCr을 구한 후 끝자리 0의 갯수를 구하는 문제가 아니며, 끝자리 숫자가 0이 나오려면 잘 생각해 보시면 2와 5의 약수를 적절하게 계산해보시면 구할 수 있다는 사실을 알 수 있습니다.

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