zmfldlwl   10달 전

최대한 시간 줄엿다고 줄엿는데도 이 문제 재귀로는 안되는 문제인가요?


ntopia   10달 전

구현하신 소스를 기준으로 설명을 드리자면

REQ(0, 1) 을 계산할 때 루프 안에서 언젠가는 REQ(1, 4) 를 부르겠죠?

마찬가지로 REQ(0, 2) 를 계산할 때도 루프 안에서 언젠가는 REQ(1, 4) 를 부르겠죠?

근데 REQ(0, 1) 안에서 REQ(1, 4) 를 부르나, REQ(0, 2) 안에서 REQ(1, 4) 를 부르나

REQ(1, 4) 가 계산해내는 값은 같을 것입니다.

근데 같은 걸 엄청나게 여러번 계산하겠죠? 그래서 시간초과가 납니다.

이 부분을 어떻게 하면 줄일 수 있을지...가 포인트 입니다.

zmfldlwl   10달 전

댓글달아주신 내용으로 생각해보면 이 문제는 재귀로는 답이 없는 문제가 맞나요? DP로 풀이해야 되는문제라고 말씀하시는거로 이해되서요.

ntopia   10달 전

DP를 재귀함수로 구현하는 테크닉도 있기 때문에 제가 아무 말도 안한거였어요..ㅋㅋ

보통 이걸 memoization 이라고 합니다.

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