[백준][DP] 9095번 1,2,3 더하기 python (200923)

1. 문제설명 

 

www.acmicpc.net/problem/9095

 

9095번: 1, 2, 3 더하기

 

 

 

2. 풀이 

 

1은 --> 1개 1

2는 --> 2개 1, 1 2

3은 --> 4개 1, 1, 1 2, 1 1, 2 3

4는  --> 7개 1,3 1,1,2 2, 2 1,1,1,1 2,1,1 1,2,1, 3,1

5는  --> 13개 1,1,1,1,1 1,1,2,1 1,2,1,1 2,1,1,1 1,1,1,2 2,2,1 1,2,2  2,1,2 3,1,1 1,3,1 1,1,3 2 3 3 2

 

 

 

 

 

 

 

 

 

 

 

 

import sys

N = int(sys.stdin.readline())
dp = [0,1,2,4]


input_num_list = []
for _ in range(N): # 입력받는 숫자의 갯수
    input_num = int(sys.stdin.readline())
    input_num_list.append(input_num)

max_num = max(input_num_list) # 제일 큰 숫자를 기준으로 채워 넣기

for idx in range(len(dp), max_num+1):
    get_num = dp[idx - 1] + dp[idx - 2] + dp[idx - 3]
    dp.append(get_num)

for num in input_num_list:
    print(dp[num])

 

 

 

 

 

import sys

N = int(sys.stdin.readline())
dp = [0,1,2,4]


input_num_list = []
for _ in range(N): # 입력받는 숫자의 갯수
    input_num = int(sys.stdin.readline())

    for idx in range(len(dp), input_num + 1):
        get_num = dp[idx - 1] + dp[idx - 2] + dp[idx - 3]
        dp.append(get_num)

    print(dp[input_num])