tngus1140   7달 전

top-down으로는 통과했고 bottom-up 방식도 될 것 같아 시도해보고 있습니다.

bottom-up으로 진행하다 아직 구하지못한 위치가 나오면 해당 위치 값을 top-down으로 구하는 방식입니다.

 

bottom-up으로 풀려다보니 어렵네요...

어떤 반례가 있을까요..?

doju   7달 전

틀리는 이유는 bottom-up 방식과는 별 관련이 없습니다. solve_recur()이 계산하고 있는 값을 다시 확인해 보세요.

여담으로 이 풀이는 bottom-up 방식이라고 할 수 없습니다. Bottom-up 방식의 핵심은 항을 계산하는 순서를 잘 설계하여 43번째 줄과 같이 점화식에 필요한 항이 아직 계산되어 있지 않은 상황이 애초에 발생하지 않도록 하는 것입니다. 이 문제를 온전히 bottom-up 방식으로 해결하는 것은 top-down 방식에 비해 꽤 어렵습니다.

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