BOJ: https://www.acmicpc.net/problem/2410


먼저 홀수의 경우 항상 1이 필요함을 알 수 있음.

그러면 그 1을 빼고 생각하면 사실상 하나 적은 수를 2의 멱수의 합으로 나타내는 것과 동일함.
따라서 n이 홀수일 때 D[n] = D[n-1] 임을 알 수 있음.


짝수일 경우 1을 몇 개 사용할 지 정하고 개수를 센다고 생각하면,
1을 0개 사용할 경우는 2 이상의 수로만 n을 만드는거니까, 전체를 2로 나누면 사실상 n/2를 합으로 표현하는 개수를 찾는것과 동일함.
마찬가지로 1을 2개 사용할 경우는 n/2-1, 4개 사용할 경우는 n/2-2, ...


이걸 코드로 나타내면 아래와 같음