백준 / 123더하기 / 9095

Question

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

Input

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

3
4
7
10

Output

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

7
44
274

Logic

기본 구조 : loop

1,2,3합을 나타내는 함수를 f(x)라 하면,

숫자	경우의수	가짓수
1	1	1
2	1+1, 2	2
3	1+1+1, 2+1, 1+2, 3	4
4	1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 3+1, 1+3	7
5	...	13
6	...	24

료 표현할 수 있다.

4의 경우의 수 세 가지로 나눠보면,

• 1+ 1의 경우의 수
• 2+ 2의 경우의 수
• 3+ 3의 경우의 수

이고, 세가지를 더한 1+2+4는 7임을 알 수 있다.

또한 가짓수 숫자들 목록 앞에 1을 붙이고 써보면,
1, 1, 2, 4, 7, 13, 24....인데, 이는 앞의 세 수를 더한 결과임을 알 수 있다.

따라서, f(x) = f(x-3) + f(x-2) + f(x-1)을 만족한다.
이를 반복문으로 나타내면 아래의 코드와 같다.

Code

from sys import stdin

def fibo2(n):
    cur1,cur2,next = 0,0,1
    for i in range(n):
        cur1,cur2,next = cur2,next,cur1+cur2+next
    return next
for i in range(int(stdin.readline())):
    N=int(stdin.readline())
    print(fibo2(N)%10007)