1, 2, 3 더하기 5 풀이

문제 링크: https://www.acmicpc.net/problem/15990

백준 알고리즘 기초 1/2 400에서 7번째 - 15990번 1, 2, 3 더하기 5를 풀어보았다.

 

풀이: 규칙 찾기가 매우 힘들었다.

파이썬은 https://ji-gwang.tistory.com/274 이 코드를 참고했다.

 

C++

 

Python

dp=[[0 for i in range(3)]for j in range(100001)]
dp[1]=[1,0,0]
dp[2]=[0,1,0]
dp[3]=[1,1,1]
for i in range(4,100001):
	dp[i][0]=(dp[i-1][1]+dp[i-1][2])%1000000009
	dp[i][1]=(dp[i-2][0]+dp[i-2][2])%1000000009
	dp[i][2]=(dp[i-3][0]+dp[i-3][1])%1000000009

t=int(input())
for i in range(t):
	n=int(input())
	print(sum(dp[n])%1000000009)

Java