[백준/Python] 9095번 1, 2, 3 더하기

---

문제

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

---

문제 이해

규칙을 찾기 위해 정수 n을 1,2,3으로 나타내는 방법의 수를 구해보았다.

처음에는 숫자 하나만 사용해도 되는지 몰라서 규칙을 찾는데 오래걸렸다.

n	ans	
1	1	
2	2 	
3	4	
4	7 	
5	13	
6	24	
7	44

 

규칙은 앞 세개의답을 더하는 것이었다.

점화식을 파악했으니 이제 문제를 풀 수 있다.

---

문제 풀이(정답)

T = int(input())

for _ in range(T):

    n = int(input())

    dp = [0] * 11

    dp[1] = 1

    dp[2] = 2

    dp[3] = 4

    for i in range(4, n+1):

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

    print(dp[n])

 

다이나믹 프로그래밍을 이용해서 문제를 풀어주었다.

 

IndexError를 방지하기위해 n이 1,2,3인 경우는 미리 설정해준다.