글 읽기 - 데이터 추가 요정합니다

만약 재귀적인 동적게획법으로 풀 시 문제 조건대로라면 N이 클 때 스택이 깊어 스택오버플로가 날 가능성이 있습니다

실제로 제가 제출한 백준에 제출한 10315066번 소스는 다른 저지 사이트의 동일 문제인

에서 스택오버플로 에러가 발생합니다

반면 반복적 동적계획법으로 푼 경우는 두 곳 모두 통과하였습니다

따라서 재귀적인 동적게획법으로 해결한 소스를 오답처리하기 위해 스택이 깊을 경우에 대한 데이터 추가가 필요합니다

코드가 공개되어 있지 않아서 확인해 보지는 못했습니다만, 백준 온라인 저지의 Java 스택 사이즈는 64 MB입니다. 즉 함수의 스택 프레임 하나가 ~6.4 KB까지 차지할 수 있습니다.

따라서 n에 대해 재귀 함수와 memoization을 사용해서 문제를 푸신 경우, 백준 온라인 저지에서는 통과되는 것이 타당하다고 생각합니다.

아 저지 사이트마다 스택 사이즈가 서로 다른가 보군요

메모리제한은 코드업쪽이 더 크게 잡혀있길래 이 문제에서 크리티컬한 tc가 부족한가 생각했었습니다

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

Baekjoon Online Judge