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

DP 유형의 문제를 풀어보자.

라고 다짐하고 문제 봤는데 이게 뭐지...? 했다...ㅎ

DP 유형이면 당연히 점화식을 만들줄 알아야 하는데.. 앞으로 꼭 차근차근 맨 처음 경우부터 일단 계산해봐야지!!!

 

테스트 케이스 개수 만큼의 입력받은 수를 1, 2, 3의 덧셈으로 표현할 때의 표현 가능한 경우의 수를 구하면 된다.

1, 2, 3일 때에는 규칙성이 보이지 않지만 4일 때부터는 규칙을 찾을 수 있다. 1과 2와 3일 때에 경우에 각각 1, 2, 3을 활용하여 다시 경우가 구해지기 때문이다.

 

9095번 1, 2, 3 더하기 풀이

#솔루션

T = int(input())

def dp(i):
  if i == 1:
    return 1
  elif i == 2:
    return 2
  elif i == 3:
    return 4
  else:
    return dp(i-1) + dp(i-2) + dp(i-3)

for _ in range(T):
  n = int(input())
  print(dp(n))

# 인풋 1 : 1 -> 1
# 인풋2 : 1+1 / 2 -> 2
# 인풋3: 1+1+1/1+2/2+1/3 -> 4
# 인풋4: 1+1+1+1/1+1+2/1+2+1/2+1+1/1+3/3+1 -> 7
# 인풋5:1+1+1+1+1/1+1+1+2/1+1+2+1/1+2+1+1/2+1+1+1/1+2+2/2+1+2/2+2+1/1+1+3/1+3+1/3+1+1/2+3/3+2 -> 13
# 인풋6:1+1+1+1+1+1/1+1+1+1+2/1+1+1+2+1/1+1+2+1+1/1+2+1+1+1/2+1+1+1+1/1+1+2+2/1+2+1+2/1+2+2+1/
#       2+1+1+2/2+2+1+1/2+1+2+1/1+1+1+3/1+1+3+1/1+3+1+1/3+1+1+1/1+2+3/2+1+3/3+2+1/3+1+2/1+3+2/2+3+1/...
        -> 24

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

9095번: 1, 2, 3 더하기