9095 1, 2, 3 더하기

https://www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

 

해결법

이 문제는 동적 프로그래밍 문제이다. 따라서 규칙이나 패턴을 찾아야 한다.

 

1: (1) => 1개
2: (1+1), (2) => 2개
3: (1+1+1), (1+2), (2+1), (3) => 4개
4: (1+1+1+1), (1+1+2), (1+2+1), (1+3), (2+1+1), (2+2), (3+1) => 7개
5: (1+1+1+1+1), (1+1+1+2), (1+1+2+1), (1+1+3), (1+2+1+1), (2+1+1+1), (1+2+2), (2+1+2), (2+2+1), (1+3+1), (3+1+1), (2+3), (3+2) => 13개
 

여기에서 패턴을 구해보면 4부터는 3+2+1의 개수를 더하면되고 5는 4+3+2의 개수를 더하면 된다.

즉, 점화식은 f(n) = f(n-1) + f(n-2) + f(n-1)이 된다.

 

코드

t = int(input())
ary = []

for i in range(t):
    ary.append(int(input()))


d = [0] * 11

def a(n):
    if n == 1:
        return 1
    elif n == 2:
        return 2
    elif n == 3:
        return 4
    
    else:
        return a(n-1) + a(n-2) + a(n-3)

for i in range(t):
    print(a(ary[i]))

따라서 점화식을 a라는 함수로 구현해서 문제를 풀었다.