1,2,3만을 이용하여 정수 n을 표현할 수 있는 경우의 수를 구하는 문제.
우선 1,2,3의 경우부터 살펴보자
1 : 1 -> 1가지
2 : 1+1, 2 -> 2가지
3 : 1+1+1, 1+2, 2+1, 3 -> 4가지
음.. 이것만 봐서는 감을 잡긴 어려운거 같다. 당시 이 문제를 풀때 7까지는 해봤던거 같다 ㅋㅋ
- 4 : 1+3 2+2 3+1 -> 4 + 2 + 1 = 7
- 5 : 1+4 2+3 3+2 4+1 -> 7 + 4 + 2 = 13
- 6 : 1+5 2+4 3+3 4+2 5+1 -> 13 + 7 + 4 = 24
- 7 : 1+6 2+4 3+4 4+3 -> 24+13+7 = 44
어떤 식으로 표현을 한 것이냐면,
우선 4를 1과 3의 합으로 표현할 수 있다는 것을 먼저 살펴보자.
이때의 3은 3일 때 경우의 수를 포함하고 있다.
1+3 => 1 + (1+1+1), 1 + (1+2), 1 + (2+1), 1 + (3) : 4가지
그럼 2+2는? 마찬가지로 2일 때의 경우의 수를 포함한다.
이처럼 계산하니 4는 7가지 경우의 수로 표현이 된다.
그럼 5이상의 수처럼 앞에 4+, 5+, ...로 표현을 하는 것도 고려를 해야할까?
- 5일 때 ( 1,2,3의 합으로만 표현하므로 4를 분해해야 한다.)
4 + 1 => (1 + 3) + 1 , ..
이건 1+4 (1 + (3 + 1)로 셌을 것이다) 에서 이미 고려를 했던 것이다!! 다시말해 중복된다.
따라서 다른 숫자들을 고려할 때도 결국 앞이 1+ ,2+ ,3+ 일 때만 고려하면 되는 것이었다.
이러면 7을 1,2,3으로만 표현하는 경우의 수는 1+6, 2+5, 3+4
즉 6일때, 5일때, 4일때의 경우의 수를 더한 것과 같다는 것을 발견할 수 있다.
코드로 구현해보면 다음과 같다
## method
def sol(num):
dp = [1 if i in (0,1) else 0 for i in range(num+1)]
for idx in range(2, num+1):
diff = 1
while diff <= 3 and num - diff >= 0 :
dp[idx] += dp[idx-diff]
diff += 1
return dp[num]
## input
n = int(input())
## output
for _ in range(n):
print(sol(int(input())))