[백준] 9095번 : 1, 2, 3 더하기

문제

나의 답안

t=int(input())
dp=[1,2,4]

for j in range(3,10):
    dp.append(dp[j-1]+dp[j-2]+dp[j-3])
    
for i in range(t):
    num=int(input())
    print(dp[num-1])

접근방법

• DP문제이므로, 규칙을 찾는 것이 중요하다.
  
  4와 5의 경우를 보면 각 n의 개수는 첫번째 전 합+두번째 전 합+세번째 전 합을 이루는 것을 알 수 있다.
  즉, dp[n]=dp[n-1]+dp[n-1]+dp[n-3]
• 문제조건에 정수 n이 주어진다. n은 양수이며 11보다 작으므로, 10까지만 구해주면 된다.

1. dp 배열에 1부터 3까지의 합을 미리 저장한다.
2. 반복문 안에서 dp에 위 식을 지정해준다. 4부터는 위의 식을 따를 수 있기 때문에 배열에 n을 3부터 10까지, 즉 배열의 인덱스는 3부터 9까지 지정해준다.
3. 반복문을 통해 테스트케이스 수(t)만큼 반복해주면서 숫자를 입력받는다. 입력받은 숫자의 개수를 dp에서 찾아 출력한다. 마찬가지로 배열의 인덱스이므로 -1해준다.