15990 - 1, 2, 3 더하기 5
문제
정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 3가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 단, 같은 수를 두 번 이상 연속해서 사용하면 안 된다.
- 1+2+1
- 1+3
- 3+1
정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.
코드
import sys
input = sys.stdin.readline
dp = [[0 for _ in range(4)] for _ in range(100000+1)]
dp[1][1] = 1
dp[2][2] = 1
dp[3][1], dp[3][2], dp[3][3] = 1, 1, 1
for i in range(4, 100000+1):
for j in range(1, 3+1):
if j < 3:
dp[i][j] = (dp[i-j][3-j] + dp[i-j][3]) % 1000000009
else:
dp[i][j] = (dp[i-j][1] + dp[i-j][2]) % 1000000009
def solve():
N = int(input())
print(sum(dp[N]) % 1000000009)
T = int(input())
for _ in range(T):
solve()한마디
굵은 글씨로 나타낸 조건을 무시하고 4를 만든다면,
- 3을 만들 수 있는 케이스에 1을 더함
- 1 + 1 + 1 + 1
- 1 + 2 + 1
- 2 + 1 + 1
- 3 + 1
- 2를 만들 수 있는 케이스에 2를 더함
- 1 + 1 + 2
- 2 + 2
- 1을 만들 수 있는 케이스에 3을 더함
- 1 + 3
7가지가 있다. 문제 조건에 따라 연속된 수를 제외하고는 3가지의 경우가 있다.
- 3을 만들 수 있는 케이스에 1을 더함
- 1 + 2 + 1
- 3 + 1
- 2를 만들 수 있는 케이스에 2를 더함
- X
- 1을 만들 수 있는 케이스에 3을 더함
- 1 + 3
dp[i][j] = (i를 만들기 위해서 맨 마지막 숫자가 j인 경우) 라고 정의한 2차원 배열을 만들어서 풀었다. 위와 같은 경우에는 아래와 같이 매칭된다.
- 3을 만들 수 있는 케이스에 1을 더함 = 4를 만들기 위해서 맨 마지막 숫자가 1인 경우
- dp[4][1] = dp[3][2] + dp[3][3] = 2
- 2를 만들 수 있는 케이스에 2를 더함 = 4를 만들기 위해서 맨 마지막 숫자가 2인 경우
- dp[4][2] = dp[2][1] + dp[2][3] = 0
- 1을 만들 수 있는 케이스에 3을 더함 = 4를 만들기 위해서 맨 마지막 숫자가 3인 경우
- dp[4][3] = dp[1][1] + dp[1][2] = 1
따라서 문제에서 주어진 조건 하에서 4를 만들 수 있는 경우의 수는 sum(dp[4]) 이다. 이렇게 점화식을 설정하고 코드를 작성했다.
