백준 (boj) 파이썬 - 1, 2, 3 더하기 (DP)

문제 링크 :https://www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

 

---

 

 

 

 

 

 

 

문제 분류 : 다이나믹 프로그래밍 https://infinitt.tistory.com/246

알고리즘 - 다이나믹 프로그래밍 (Dynamic Programming)

 

 

N을 나타내는 방법의 개수를 DP라는 배열에 담기로 한다.

따라서 정수 N을 1,2,3 더하기로 나타내는 방법은 DP[N]이라고 한다.

 

* 점화식

입력된 정수 N을 ( = DP[N]) 나타내는 방법

• DP[N-1] 에 1을 더한다.
• DP[N-2] 에 2를 더한다.
• DP[N-3] 에 3을 더한다.

이렇게 3가지 방법으로 DP[N] 를 나타 낼 수 있다.

즉, 점화식으로 쓰면 DP[N] = DP[N-1] + DP[N-2] + DP[N-3]

 

* 정답코드 (Python)

tk = int(input())
for _ in range(tk):

	n = int(input())
	dp = [0 for _ in range(n+1)]
	if n<3:
		print(n)
	else:
		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])