[백준/BOJ][Python] 9095번 1, 2, 3 더하기

[백준/BOJ][Python] 9095번 1, 2, 3 더하기

문제

정수 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의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력

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

출력

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

예제 입력 1 

3
4
7
10

예제 출력 1 

7
44
274

 

---

생각한 과정

DP 배열을 만들었을 때, 각각 1, 2, 3을 만들 수 있는 방법의 수는 1, 2, 4가지라고 생각을 했다.

( arr[1] = 1, arr[2]는 1 + 1과 2 자체를 더하는 방법으로 2가지, arr[3]은 1+1+1, 2+1, 1+2, 3으로 4가지이다.)

 4를 만들 수 있는 방법은

1+1+1+1, 1+1+2, 1+2+1, 1+3, 2+1+1, 2+2, 3+1 즉, arr[1] + arr[2] + arr[3]이다.

 

따라서 arr[ i ]  = (arr[i - 1]에서 1을 더하는 경우) + (arr[i - 2]에서 2를 더하는 경우) + (arr[i - 3]에서 3을 더하는 경우) 이다.

 

그럼 5를 만들 수 있는 방법은 arr[2] + arr[3] + arr[4]가 된다.

 

 

arr[ i ] = i 를 1 , 2 , 3 의 합으로 나타내는 방법의 수이므로

arr[ i ] = arr[i - 1] + arr[i - 2] + arr[i - 3]

 

---

코드

T = int(input())
arr = [0]*12
arr[1] = 1
arr[2] = 2
arr[3] = 4

for _ in range(T):
    x = int(input())
    for i in range(4, x+1):
        arr[i] = arr[i-1] + arr[i-2] + arr[i-3]
    print(arr[x])