[알고리즘]BOJ_9095_1,2,3 더하기(파이썬 다이나믹 프로그래밍, continue, 나머지 연산)

#문제링크

9095번: 1, 2, 3 더하기 (acmicpc.net)

9095번: 1, 2, 3 더하기

 

#문제

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

1, 2, 3 더하기

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초 (추가 시간 없음)	512 MB	58213	37350	24785	62.116%
문제
정수 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

 

#답안

import sys
input=sys.stdin.readline

#테스트케이스 개수 t를 입력받는다.
t=int(input())



#for문을 돌리며 정수 n을 t개 입력받는다.
for _ in range(t) :
    n=int(input())

    # dp테이블로 쓸 리스트를 생성하고 0으로 초기화한다.
    dp = [0] * (n + 1)  # 1부터 사용할 것이므로 n+1의 크기로 초기화해야한다.

    #for을 4부터 n까지 돌린다.
    for i in range(1,n+1) :
        if i==1 :
            dp[1] = 1
            continue
        elif i==2 :
            dp[2] = 2
            continue
        elif i==3 :
            dp[3] = 4
            continue

        dp[i]=dp[i-1]+dp[i-2]+dp[i-3]
    print(dp[n])

▲답안 설명