iljimae   1년 전

solve(n,prev)를 전에 사용했던 숫자가 prev일때 n을 만들 수 있는 경우의 수라고 정의하고 풀었는데 시간초과가 납니다. 어떤 방법으로 접근해야 시간안에 해결할 수 있을까요? 도와주세요 

jseo   1년 전

두가지 방법이 있습니다.

1. 작성자님이 정의하신대로 풀 수도 있습니다만, 탑 다운 방식으로는 힘들수도 있습니다. 바텀업으로 바꿔 보시고, 세번쩨 루프를 제거할 방법을 찾아보세요.

2. 사실 파티션 문제는 워낙 유명한 문제여서 관련된 여러가지 정리들이 많습니다. 그 중 하나가 오일러가 증명한 정리인데, 

# partitions into distinct parts = # partitions into odd parts

odd parts partition을 구하는 문제는 쉽게 풀 수 있죠.

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