반응형
DP는 나열이 반이다. 잘 나열하는게 시작이다.
그럼 1부터 5정도까지만 나열해보자.
| 1 | 2 | 3 | 4 | 5 |
| 1 | 1+1 2 |
1+1+1 1+2 2+1 3 |
1+1+1+1 1+1+2 1+2+1 1+3 2+1+1 2+2 3+1 |
1+1+1+1+1 1+1+1+2 1+1+2+1 1+1+3 1+2+1+1 1+2+2 1+3+1 2+1+1+1 2+1+2 2+2+1 2+3 3+1+1 3+2 |
| 1개 | 2개 | 4개 | 7개 | 13개 |
이를 통해 알 수 있는 것은
어떤 수를 더하기로 나타낼 땐, 1,2,3을 각각 앞에 적고 +를 붙인 뒤에 오는 숫자들은 이전 수의 갯수와 동일하다는 것이다.
예를 들어 5의 경우,
1로 시작하는 경우는
1+ 뒤에 오는 모든 숫자들은 4의 경우와 똑같다.
2로 시작할때는 2+뒤에 오는 숫자들은 3의 경우와 똑같다.
3으로 시작할때는 3+2의 경우이다.
따라서 일반항으로 나타내면
T(k)=T(k-1)+T(k-2)+T(k-3)이다.
아 이 문제에서 주의해야 할점은 나머지를 구하지 않으면 메모리초과가 발생한다는 점이다.
숫자가 기하급수적으로 커지기 때문이다. C와 같은 경우는 오버플로우가 발생하고, 파이썬은 메모리 초과 문제가 발생한다.
아래는 코드이다.
import sys
input=sys.stdin.readline
t=int(input())
dp=[0,1,2,4]
for _ in range(t):
x= int(input())
for k in range(len(dp),x+1):
if k>len(dp)-1:
dp.append((dp[k-3]+dp[k-2]+dp[k-1])%1000000009)
print(dp[x])
반응형
