March 1, 2023

문제 요약

• 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수
• 시간 제한 : 1초
• 1 ≤ n ≤ 10,000

풀이

n = int(input())
num_list = [int(input()) for _ in range(n)]
max_num = max(num_list)
dp = [[0] * 4 for _ in range(max_num + 1)]
dp[1][1] = 1
dp[2][1] = 1
dp[2][2] = 1
dp[3][1] = 1
dp[3][2] = 1
dp[3][3] = 1

for i in range(4, max_num + 1):
    for j in range(1, 4):
        count = 0
        for k in range(1, j + 1):
            count += dp[i - j][k]
        dp[i][j] = count

for num in num_list:
    print(sum(dp[num]))

• DP 이용
• 2중 배열에 어떤 수를 몇 이하의 수의 합으로 표현하는 방법의 수가 몇 가지 존재하는지 기록