[백준 파이썬] # 9095 1, 2, 3 더하기

Silver III

# 9095 1, 2, 3 더하기

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

9095번: 1, 2, 3 더하기

 

풀이

T = int(input())

for i in range(T):
    n = int(input())
    dp = [0] * (n+3)
    dp[0] = 1
    dp[1] = 2
    dp[2] = 4
    for i in range(3, n):
        dp[i] = dp[i-3] + dp[i-2] + dp[i-1]
    print(dp[-4])

 

후기

• 동적 프로그래밍 문제라는 것을 캐치하면 규칙성을 발견할 수 있다
  (동적 프로그래밍 문제인지 여부를 빠르게 파악하는 방법이 있었으면 좋을 듯)
  
  
• dp 리스트에 각 값을 기록해보면 dp[i] = dp[i-3]+dp[i-2]+d[i-1] 임을 알 수 있다. 이를 이용해 풀이를 코드를 구성하면 정답..!