백준 15990
정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하기.
- 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 3가지가 있다.
- 합을 나타낼 때는 수를 1개 이상 사용해야 한다.
- 단, 같은 수를 두 번 이상 연속해서 사용하면 안 된다.
- 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 100,000보다 작거나 같다.
- 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다.
입출력
| 입력 | 출력 |
|---|---|
| 3 4 7 10 | 3 9 27 |
접근 방식
:
알게된 점
<DP로 풀기>
예를 들어 4를 만드는 가짓수를 구한다면 가능한 경우는 1, 2, 3을 만드는 경우 각각 끝에 3, 2, 1을 더해 만들 수 있다. 이 때 주의해야할 점은 3을 더할 때는 1을 만드는 케이스들 중 끝에 3이 오는 경우는 배제해주어야 한다. 2와 1을 더해줄 때도 마찬가지이다.
따라서 dp[i][j]가 i를 만드는 데, 더해줄 때 끝에 오는 수가 j인 경우의 수를 뜻한다면,
dp[4][1] = dp[3][3] + dp[3][2] -> 끝이 1인 4를 만드는 경우 = 끝이 3인 3을 만드는 경우 + 끝이 2인 3을 만드는 경우
dp[4][2] = dp[2][3] + dp[2][1]
dp[4][3] = dp[1][1] + dp[1][2] 이다.
코드
dp = [[0, 0, 0, 0] for _ in range(100001)]
dp[1] = [0, 1, 0, 0]
dp[2] = [0, 0, 1, 0]
dp[3] = [0, 1, 1, 1]
for i in range(4, 100001):
dp[i][1] = (dp[i-1][3] + dp[i-1][2]) % 1000000009
dp[i][2] = (dp[i-2][3] + dp[i-2][1]) % 1000000009
dp[i][3] = (dp[i-3][1] + dp[i-3][2]) % 1000000009
m = int(input())
for _ in range(m):
n = int(input())
print(sum(dp[n]) % 1000000009)주의해야할 점은 각 케이스마다 1000000009로 나눈 나머지를 저장하고, 합계를 구할 때에도 1000000009로 나눈 나머지를 구해야 한다는 점이다.
