백준 9095(1,2,3 더하기) - Python(파이썬)

9095번: 1, 2, 3 더하기

* 내가 생각한 풀이 *

예제 풀이 

dp[1]	dp[2]	dp[3]	dp[4]	dp[5]	dp[6]	dp[7]	dp[8]	dp[9]	dp[10]
1	dp[1] +dp[2] =2	dp[1] +dp[2] +dp[3] =4	dp[1] +dp[2] +dp[3] =7	dp[2] +dp[3] +dp[4] =13	dp[3] +dp[4] +dp[5] =24	dp[4] +dp[5] +dp[6] =44	dp[5] +dp[6] +dp[7] =81	dp[6] +dp[7] +dp[8] =149	dp[7] +dp[8] +dp[9] =274

💻 Python(파이썬)

import sys
t = int(sys.stdin.readline())
array = [int(sys.stdin.readline()) for _ in range(t)]
dp = [0]*11
dp[1]=dp[2]=dp[3]=1
for i in range(11):
    if i+1<=10:
        dp[i+1]+=dp[i]
    if i+2<=10:
        dp[i+2]+=dp[i]
    if i+3<=10:
        dp[i+3]+=dp[i]

for i in array:
    print(dp[i])

---

다른 사람 풀이

예제 풀이

예제의 답을 구하는 법은 다음과 같다

dp[1]	dp[2]	dp[3]	dp[4]	dp[5]	dp[6]	dp[7]	dp[8]	dp[9]	dp[10]
1	1+1,2 -> 2	1+1+1, 1+2, 2+1, 3 -> 4	dp[1] +dp[2] +dp[3] =7	dp[2] +dp[3] +dp[4] =13	dp[3] +dp[4] +dp[5] =24	dp[4] +dp[5] +dp[6] =44	dp[5] +dp[6] +dp[7] =81	dp[6] +dp[7] +dp[8] =149	dp[7] +dp[8] +dp[9] =274

문제 풀이

① i=0인 경우 0, i=1인 경우 1, i =2인 경우 2, i=3인 경우 4라고 지정하기
② i=3이후에 숫자는 dp[i-3]+dp[i-2]+dp[i-1]의 규칙을 사용하여 구한다.

💻 Python(파이썬)

import sys
t = int(sys.stdin.readline())
array =[0,1,2,4]
for i in range(4,11):
    array.append(array[i-3]+array[i-2]+array[i-1])

for i in range(t):
    n = int(sys.stdin.readline())
    print(array[n])