1,2,3 더하기 [백준 9095] - python

import sys
input = sys.stdin.readline

def BOJ9095() :
  T = int(input())

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

BOJ9095()

 

접근 방법 :

 

dp 문제이다.
4를 만드는 경우의 수부터 접근 해보자.

    4는
     1. 1을 만드는 경우의 수들에서 3하나를 추가해주면 된다
     2. 2를 만드는 경우의 수들에서 2하나를 추가해주면 된다
     3. 3을 만드는 경우의 수들에서 1하나를 추가해주면 된다
    4를 만드는 경우의 수는 1을 만드는 경우의 수 + 2를 만드는 경우의 수 + 3을 만드는 경우의 수 이다.

 

dp[i] = dp[i-3] + d[i-2] + dp[i-1] 이런 점화식이 만들어지게 되므로 이걸 그대로 적용하면 된다

 

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

9095번: 1, 2, 3 더하기