[BOJ_9095] 1, 2, 3 더하기

정수 n을 입력 받아서, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 문제입니다.

 

1, 2, 3이라는 숫자가 고정이 되어 있습니다.

 

규칙을 찾아봅시다.

n	1	2	3	4	5
경우의 수	1	2	4	7	?

네번째 까지 구한 결과

f(1) + f(2) + f(3) = f(4)가 성립합니다

 

다섯번째 까지만 수동으로 구해봅시다

11111

1112

1121

1211

2111

122

212

221

113

131

311

23

32

총 13가지입니다.

f(2) + f(3) + f(4) = f(5) 가 성립하므로

 

f(n) = f(n-3) + f(n-2) + f(n-1)

로 점화식을 도출할 수 있습니다.

dp = [0 for _ in range(11)]
dp[1] = 1
dp[2] = 2
dp[3] = 4

for i in range(4, 11):
	dp[i] = dp[i-3] + dp[i-2] + dp[i-1]

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

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

for i in n:
	print(dp[i])

※ 여기서 테스트 케이스를 몇 번인지 받아와서

이 횟수만큼 리스트에 입력받아서 넣어주는 패턴을 기억해두면 좋을 것 같습니다.

 

www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기