백준 9095 문제 풀이 python

🐒 1, 2, 3 더하기

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

✍ 나의 풀이

import sys

dp = [0] * 11

dp[1] = 1
dp[2] = 2
dp[3] = 4

for i in range(4,11):
    dp[i] = dp[i-3] + dp[i-2] + dp[i-1]

t = int(input())

for _ in range(t):
    n = int(sys.stdin.readline().rstrip())
    print(dp[n])

어떻게 풀어야할지 몰라서 다른 사람들의 풀이를 봤는데, 세번쩌 전 항과 두번째 전항과 이전항의 합이 현재항의 값이 되는 규칙이 있었다. 마치 피보나치 수열처럼

---

🧠 문제 이해

n이 최대 10 밖에 안되므로
미리 1부터 10까지 경우의 수를 계산해 놓고
입력되는 정수에 따라서 경우의 수를 출력해준다.

DP 테이블

dp = [0] * 11 
	 # 1부터 n까지 1,2,3의 합으로 나타낼 수 있는 경우의 수를 저장할 리스트를 만든다.
	# n은 양수이며 11보다 작다

dp[1] = 1
dp[2] = 2
dp[3] = 4

for i in range(4,11):
    dp[i] = dp[i-3] + dp[i-2] + dp[i-1]
 # 반복문으로 이전항을 이용해 1부터 10까지의 경우의 수를 저장한다.

DP테이블에 모든 경우의 수를 담았으니

입력되는 값에 따라 출력만 해주면 된다.

t = int(input())

for _ in range(t):
    n = int(sys.stdin.readline().rstrip())
    	# 반복문에서 받는 입력은 readline()이 처리가 빠르다
    print(dp[n])