백준 파이썬 9095번 1, 2, 3 더하기 (Today I Learn 2024.11.04)

2024/11/04 백준 파이썬 공부
9095번 1, 2, 3 더하기

1) 문제
정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 
합을 나타낼 때는 수를 1개 이상 사용해야 한다.

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

2) 입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 
각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. 
n은 양수이며 11보다 작다.

3) 출력
각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

4) 코드

T = int(input())
num = [0, 1, 2, 4]

for i in range(T):
    n = int(input())
    
    for j in range(3, n):
        if j >= len(num)-1:
            num.append(num[j-2] + num[j-1] + num[j])
    
    print(num[n])

5) 문제 해설
1의 표현법: 1 >> 1개
2의 표현법: 1+1, 2 >> 2개
3의 표현법: 1+1+1, 1+2, 2+1, 3 >> 4개
4의 표현법: 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 1+3, 3+1, 2+2 >> 7개
...

>> 점화식
num[n] = num[n-1] + num[n-2] + num[n-3]

따라서, 1, 2, 3의 표현하는 방법의 수를 저장해 놓고, 갱신을 하면서, 해당 수의 표현 방법 수를 계산한다.


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