백준 | 1, 2, 3 더하기 4

백준 1, 2, 3 더하기 4

1부터 5까지 자연수에 대해 주어진 조건을 만족하는 조합을 오름차순(즉, 중복 제거)으로 정렬하면 다음과 같다.

1: 1
2: 1+1, 2
3: 1+1+1, 1+2, 3
4: 1+1+1+1, 1+1+2, 2+2, 1+3
5: 1+1+1+1+1, 1+1+1+2, 1+2+2, 1+1+3, 2+3

여기서, dp[i]를 [0, 1로 끝나는 방법의 수, 2로 끝나는 방법의 수, 3으로 끝나는 방법의 수]로 정의하면 다음과 같은 점화식을 세울 수 있다.

dp[i][1] = dp[i - 1][1]
dp[i][2] = dp[i - 2][1] + dp[i - 2][2]
dp[i][3] = dp[i - 3][1] + dp[i - 3][2] + dp[i - 3][3]

맨 뒤에 +1을 붙여 i를 만들 수 있는 경우는, i - 1을 만들 수 있는 경우 중 1로 끝나는 경우와 같다. 왜냐면 숫자를 오름차순으로 정렬하여 중복을 제거하기로 약속했기 때문이다.

같은 논리로..

+2를 붙여 i를 만들 수 있는 경우는, i - 2를 만들 수 있는 경우 중 1로 끝나거나 2로 끝나는 경우를 더한 값이다.
+3를 붙여 i를 만들 수 있는 경우는, i - 3을 만들 수 있는 경우 중 1로 끝나거나 2로 끝나거나 3으로 끝나는 경우를 모두 더한 값이다.

추가로 각 케이스마다 dp를 계산하면 시간 초과가 떠서, n의 최댓값인 10,000을 기준으로 dp를 한 번만 계산하였다.

import sys

# 점화식 계산
dp = [[0, 0, 0, 0] for _ in range(10001)]
dp[1] = [0, 1, 0, 0]    # 1: 1
dp[2] = [0, 1, 1, 0]    # 2: 1 + 1, 2
dp[3] = [0, 1, 1, 1]    # 3: 1 + 1 + 1, 1 + 2, 3

for i in range(4, 10001):
    dp[i][1] = dp[i - 1][1]
    dp[i][2] = dp[i - 2][1] + dp[i - 2][2]
    dp[i][3] = dp[i - 3][1] + dp[i - 3][2] + dp[i - 3][3]

# 입력 및 출력
t = int(sys.stdin.readline())
for _ in range(t):
    n = int(sys.stdin.readline())
    
    print(sum(dp[n]))

dp[i]를 조건에 맞게 i를 표현할 수 있는 경우의 수로 정의하면, 아래와 같은 풀이도 가능하다.

import sys

# 점화식 계산
# dp[i]: 조건에 맞게 i를 표현할 수 있는 경우의 수
# dp[0]의 경우, 아무것도 선택하지 않은 경우도 1가지 방법으로 치기 위해 1로 초기화한다.
dp = [1 for _ in range(10001)]

# 2를 추가하는 방법 누적
for i in range(2, 10001):
    dp[i] += dp[i - 2]

# 3을 추가하는 방법 누적
for i in range(3, 10001):
    dp[i] += dp[i - 3]

# 입력 및 출력
t = int(sys.stdin.readline())
for _ in range(t):
    n = int(sys.stdin.readline())
    print(dp[n])