9095: 1,2,3 더하기

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

9095번: 1, 2, 3 더하기

설명

우선, 정수 n이 주어졌을 때 n을 1,2,3,의 합으로 나타내는 방법의 수를 구하는 프로그램 작성하시오.

정수 n은 양수이며 11보다 작다. (1<=n<10)

핵심 아이디어

• 다이나믹 프로그래밍(dp)
• 다이나믹 프로그래밍은 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것으로 하나의 문제 해결 패러다임으로 볼 수 있다. 

패턴을 찾아서 점화식을 구하면 아래와 같다.

# 패턴찾기
dp[1] = 1
dp[2] = 2: 1+1, 2 
dp[3] = 4: 1+1+1, 1+2, 2+1, 3 
dp[4] = 7: 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3, 3+1, 
dp[5] = 13: 1+1+1+1+1, 1+1+1+2 *4개, 2+2+1 * 3개, 3+1+1*3개, 3+2 * 2개
...

dp[4]를 살펴보면 dp[4] = dp[3] + dp[2] + dp[1] = 4 + 2 + 1 = 7이 됨을 알 수 있다. 따라서, i >= 4일 때, dp[i] = dp[i-1] + dp[i-2] + dp[i-3]이 됨을 알 수 있다. 

구현 코드

# 테케 수 입력받기
t = int(input())

for _ in range(t):
	# 정수 n 입력받기
	n = int(input())
	# dp 테이블 초기화
	dp = [0] * (n+1) # 1부터 시작

	for i in range(1, n+1):
		if i == 1:
			dp[i] = 1
		elif i == 2:
			dp[i] = 2
		elif i == 3:
			dp[i] = 4
		else:
			dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
	print(dp[n])

다른 풀이

t = int(input())
for _ in range(t):
	n = int(input())

	# DP 테이블 초기화
	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])