백준 15988번(파이썬):1, 2, 3 더하기 3
백준 15988번 문제 정리글 입니다.
문제 출처-https://www.acmicpc.net/problem/15988
문제 내용
나의 풀이
T=int(input())
num=[]
for i in range(T):
num.append(int(input()))
dp=[0]*(max(num)+1)
dp[1],dp[2],dp[3]=1,2,4
for i in range(T):
if dp[num[i]]!=0:
continue
for j in range(4,num[i]+1):
if dp[j]!=0:
continue
dp[j]=(dp[j-1]+dp[j-2]+dp[j-3])%1000000009
for i in range(T):
print(dp[num[i]])
- 임의의 정수 n에대해서 d[n]은 n을 1,2,3 의 합으로 만들 수 있는 방법의 수를 1,000,000,009로 나눈 나머지로 정의했다.
- n>=4일 때, 점화식 dp[j]=dp[j-1]+dp[j-2]+dp[j-3]을 만족한다.
점화식의 조건과 식을 구해서 해결했지만 시간이 오래걸렸다.
다른 풀이
T=int(input())
dp=[0,1,2,4]
l=4
for i in range(T):
n=int(input())
while n>=l:
dp.append((dp[l-1]+dp[l-2]+dp[l-3])%1000000009)
l+=1
print(dp[n])
\(l\)=4라는 임의의 변수를 선언하여 반복문을 통해 4이상의 수만 점화식을 통해 값을 구하도록 더 간단히 구현했다.
입력을 받으며 바로 계산을 한다면 더욱 쉽게 해결할 수 있었다.
