백준 9095번 1,2,3 더하기

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

 

규칙을 찾아내기 위해 경우의 수를 세봤다.

정수	합을 나타내는 방법의 수
1	1
2	2
3	4
4	7
5	13

 

4의 합을 나타내는 방법의 수는 1,2,3의 합을 나타내는 방법의 수의 합이고 

5의 합을 나타내는 방법의 수는 2,3,4의 합을 나타내는 방법의 수의 합이다.

 

일반화 하면 n의 합을 나타내는 방법의 수는 n-1,n-2,n-3의 합을 나타내는 방법의 수의 합이다.

이를 이용하여 코드를 짠다.

 

저번 백준 과제를 하면서 알게 된 dp 동적 프로그래밍을 사용하면 된다.

코드에 추가적인 주석을 달아놨다.

T = int(input())

# 0부터 10까지의 숫자를 만들기 위한 경우의 수를 저장할 리스트를 생성
# 초기값으로 1, 2, 3을 만드는 경우의 수를 설정
d = [0] * 11  
d[1] = 1 
d[2] = 2  
d[3] = 4  

# 4부터 10까지의 숫자를 만들기 위한 경우의 수를 계산하여 리스트에 저장
for i in range(4, 11):
    d[i] = d[i - 3] + d[i - 2] + d[i - 1]

for i in range(T):
    n = int(input())  # 입력값으로 숫자를 받음
    print(d[n])  # 숫자를 만드는 경우의 수를 출력