rktkek456   6년 전

재귀함수로 짰는데

막상 다 짜놓고 보니까

최악의 경우 앞 행성까지 무조건 1씩 진행하게 될경우 시간이 기하급수적으로 증가한다는 걸 알게 됐습니다.

조건을 줘서 중간에 재귀를 강제로 종료시키는 방법이 있을까요?

아니면 아예 접근이 잘못된걸까요?

아 dp로도 짜봤는데 메모리 초과가 나더라구요...

y305205   6년 전

공식을 한번 만들어 보세요!!

재귀 함수의 경우에는 필요하지 않은 중간 과정을 처음부터 끝까지 밟아야하기 때문에 많은 경우에 시간 초과가 날 것이고,

전 이 점에서 착안해서 다이나믹 프로그래밍으로 문제를 풀려고 했더니 메모리 용량이 터져버리더라고요..ㅡ.,ㅡ 당연히 일어날 일이었는데 너무 바보같이 생각했습니다.

이 문제의 경우에는 재귀를 쓰지 않고도 공식으로 해결하는 방법이 제일 좋은 방법이라고 생각합니다. 1부터 이어나가면서 써보시면 패턴이 보일거에요!

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