[백준]15990 1, 2, 3더하기 5 파이썬 python

문제링크

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

15990번: 1, 2, 3 더하기 5

코드

import sys
input = sys.stdin.readline
mod=1000000009
MAX = 100001
d = [[0]*4 for _ in range(MAX)]
d[1]=[0,1,0,0] 
d[2]=[0,0,1,0]
d[3]=[0,1,1,1]
for i in range(4,MAX):
    d[i][1] = (d[i-1][2]+d[i-1][3])%mod
    d[i][2] = (d[i-2][1]+d[i-2][3])%mod
    d[i][3] = (d[i-3][1]+d[i-3][2])%mod
 
t = int(input())
for _ in range(t):
    n = int(input())
    print((d[n][1]+d[n][2]+d[n][3])%mod)

 

POINT

- DP로 접근

- 풀이방법:

연속된 수를 방지하기 위해서 마지막 수를 저장하고 있어야 한다. 

n번째에서 할 수 있는 행동은 총 3가지 : +1, +2, +3 추가하기

단 이때, 다음과 같은 조건이 추가된다. 

+1 : 바로 앞 수가 1이면 안됨 / +2 : 바로 앞 수가 2이면 안됨 / +3 : 바로 앞 수가 3이면 안됨

 

이를 구현하기위해서 2차원 배열 d[i][j] 생성

d[i][j] = '총합이 i이고 맨마지막 수가 j인 배열의 갯수' 라고 정의 

ex) d[3][2] : 총 합이 3이고, 맨마지막 수가 2인 배열의 갯수  --> {1,2} 만 존재하므로 d[3][2]=1

 

이후, d[i][1] = d[i-1][2]+d[i-2][3] 와 같은 방식으로 저장해나간다.

i를 만들기 위해 맨 마지막 수에 1을 사용하려면, 총 합이 i-1인 배열에 1을 더해서 (i-1) + 1 = i를 만든다.

하지만 1을 연속으로 사용할 수 없기 때문에, 총 합이 (i-1)인데 마지막 수가 2(= d[i-1][2]) 혹인 3(=d[i-2][3]) 으로 구성된 배열만 사용할 수 있다. 

 

예를 들어, 4를 만들기 위해 맨 마지막에 1을 사용하려면(=d[4][1]) 총합이 3인 배열을 사용하는데,

이때 d[3][1]은 1이 중복되기 때문에 사용불가하고, d[3][2]과 d[3][3]만 사용가능하다.