[BOJ] 9095 / 1, 2, 3 더하기 / Python

[BOJ] 9095 / 1, 2, 3 더하기 / Python

[BOJ] 9095 / 1, 2, 3 더하기 / Python

www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

 

풀이

제한된 조건으로 경우의 수를 구하는 문제이다.

경우의 수를 발생 시키는 일정한 규칙을 찾고 규칙에서 점화식을 찾아 해결 하였다.

N = 1 -> 1
N = 2 -> 2
N = 3 -> 4
N = 4 -> 7
N = 5 -> 13

위의 규칙으로 구한 점화식은

dp(N) = dp(N-1) + dp(N-2) + dp(N-3)

점화식을 이용하여 Tabluation 으로 문제를 해결 하였다.

T = int(input())

for _ in range(T):
    N = int(input())
    
    dp = [0, 1, 2, 4] + [0] * N
    
    for i in range(4, N+1):
        dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
    print(dp[N])