문제
정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.
- 1+1+1+1
- 1+1+2
- 1+2+1
- 2+1+1
- 2+2
- 1+3
- 3+1
정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 1,000,000보다 작거나 같다.
각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다.
아이디어
정수 1 -> 1가지
1
-----------------------
정수 2 -> 2가지
1, 1
2
-----------------------
정수 3 → 4가지
1, 1, 1
1, 2
2, 1
3
정수 4 → 7가지
1, 1, 1, 1
1, 1, 2
1, 2, 1
2, 1, 1
2, 2
1, 3
3, 1
정수 5 → 13 = 1 + 4 + 3 + 3 + 2
1, 1, 1, 1, 1
1, 1, 1, 2
1, 1, 2, 1
1, 2, 1, 1
2, 1, 1, 1
1, 1, 3
1, 3, 1
3, 1, 1
2, 2, 1
2, 1, 2
1, 2, 2
3, 2
2, 3
정수 6 → 24가지 = 1 + 5 + 4 + 6 + 6 + 1 + 1
1, 1, 1, 1, 1, 1 (1가지)
1, 1, 1, 1, 2 (5가지)
...
1, 1, 1, 3 (4가지) : combination (4, 1) = 4
....
1, 1, 2, 2 (6가지) : combination (4, 2) = 6
1, 2, 2, 1
2, 2, 1, 1
1, 2, 1, 2
2, 1, 2, 1
2, 1, 1, 2
1, 2, 3 (6가지)
1, 3, 2
2, 1, 3
2, 3, 1
3, 1, 2
3, 2, 1
2, 2, 2 (1가지)
3, 3 (1가지)
html
정수 7 -> 38가지 = 1 + 6 + 10 + 5 + 4 + 6 + 3 + 3
1, 1, 1, 1, 1 , 1, 1
1, 1, 1, 1, 1, 2 (6가지)
....
1, 1, 1, 2, 2 (10가지) : combi (5, 3) = combi (5, 2) = 10
....
1, 1, 1, 1, 3 (5가지)
....
1, 1, 1, 3 (4가지)
....
1, 1, 2, 2 (6가지)
....
1, 3, 3 (3가지)
....
2, 2, 3 (3가지)
....
이를 통해 규칙을 찾아보면 다음과 같다.
d[i] = d[i-1] + d[i-2] +d[i-3].
단, i \ge 3
1000000009로 나눈 나머지를 값으로 하는 이유 : 지나치게 커지는 것을 방지.
정수의 성질을 이용해 a\; \%\; c + b\; \%\; c = (a+b)\; \%\; c 를 응용한다.
이를 점화식에 적용하면 다음과 같다.
d[i] % 100 = d[i-1] % 100 + d[i-2] % 100 + d[i-3] % 100
코드
python
import sys
input = sys.stdin.readline
num = 1000000009
dp = [1, 2, 4]
# 1번째, 2번째, 3번째 값만 미리 설정
for _ in range(int(input())):
n = int(input())
for i in range(len(dp), n):
dp.append(dp[i-1] % num + dp[i-2] % num + dp[i-3] % num)
print(dp[n-1] % num)