[PS] BOJ159990 1,2,3 더하기 5 ( DP ) With 파이썬

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

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

 

◎문제풀이

 

기저조건( +1, +2, +3)이 주어지고 목표(정수 n)의 구하는 경우의 수를 구하는 문제이므로 DP이다. 

 

 

n이 10이라고 가정하고 +1,+2,+3으로 10을 만드는 방법의 수를 d[10]이라고 해보자. 이때 사건은 총 3가지이다. 

 

첫번째 사건 : +1로 끝나는 경우 = d[9]

두번째 사건 : +2로 끝나는 경우 = d[8]

세번째 사건 : +3으로 끝나는 경우 = d[7]

 

세 가지 사건은 독립사건이다. 그러므로 점화식은 아래와 같다. 

 

d[10] = d[9] + d[8] + d[7] 

 

그런데 조건이 하나 있다. 같은 수를 두 번이상 연속해서 사용하면 안된다. 

 

d[9]에서 +1로 끝나는 경우의 수를 제외해야 한다.

d[8]에서 +2로 끝나는 경우의 수를 제외해야 한다.

d[7]에서 +3으로 끝나는 경우의 수를 제외해야 한다. 

 

이는 이차원 자료구조로 쉽게 구현이 가능하다. 

 

d[1] 은 +1 하나이다.  d[1]은 [1.0.0]이다.

d[2] 는 +2 하나이다. d[2]는 [0.1.0]이다.

d[3]은 1+2, 2+1, +3이다. +1, +2,+3로 끝나는 경우의 수가 모두 하나씩 있으니 [1,1,1]이다.

 

인덱스 0 : +1로 끝나는 경우의 수

인덱스 1 : +2로 끝나는 경우의 수 

인덱스 2 : +3으로 끝나는 경우의 수

 

이렇게 인덱스 별로 경우를 나누어 놓으면 경우의 수 계산이 쉬워진다. 예를들어,

 

6 = d[3] + 3 

 

6을 만드는데 +3이 쓰였으므로 d[3]에서 +3의 경우는 제외해야 한다. 

 

+3이 다음의 d[3]의 값 =  d[3][0] + d[3][1]

 

 

◎코드

#BOJ15990 1,2,3 더하기 5
import sys
input = sys.stdin.readline

t = int(input())
d = [ [0,0,0] for _ in range(100001) ] 

d[1] = [1,0,0]
d[2] = [0,1,0]
d[3] = [1,1,1]

#BOTTOM-UP
for i in range(4,100001) :
  d[i][0] = (d[i-1][1] + d[i-1][2])%1000000009
  d[i][1] = (d[i-2][0] + d[i-2][2])%1000000009
  d[i][2] = (d[i-3][0] + d[i-3][1])%1000000009
     
for _ in range(t) :
  n = int(input())
  print(sum(d[n])%1000000009)

 

테스트케이스마다 결과를 구해야 하므로 n의 최대값인 100,000까지 모두 연산해놓아도 된다. 시간제한이 1초이므로 for문으로 100,000은 충분히 가능하다.