[Python] 백준 20544 - 공룡게임

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

풀이

풀고 나서 보니까 많은 분들이 2차원, 혹은 4차원(!) dp를 구현하여 고통을 호소하고 계셨다.

허나 이 문제는 단순 수학 점화식 풀듯이 일차원 dp로 쉽게 풀 수 있다.(이걸로 숏코딩도 쉽게 할 수 있다)

아래에서는 그 풀이를 소개하고자 한다.

 

구하고자 하는 값을 $a_n$이라고 하자.

$a_n$은 마지막 부분에 어떤 종류의 장애물이 오느냐에 따라 아래와 같이 점화식으로 표현 할 수 있다.

근데 그냥 단순히 $a_{n}=a_{n-1}+2\times a_{n-2} +3\times a_{n-3}$ 라고 표현하면 빨간 글씨처럼 '누락되는 부분'이 있다.

 

바로, 0101101.....02와 같이 마지막 부분 전까지는 0과 1과 나오는 상황이다.

 

 

그래서 이 케이스를 따로 더해주기 위해, 0과 1로만 이루어지면서 조건을 만족하는(2가 반드시 포함되어야 한다는 조건 제외) $b_n$을 따로 구하자.

 

 

$b_n$의 마지막에 오는 장애물의 종류에 따라 위 그림과 같이 경우가 나누어지고, 점화식은 $b_{n}=b_{n-1}+b_{n-2} + b_{n-3}$과 같이 세울 수 있다.

 

그래서 진짜 최종 점화식은, 

$a_{n}=a_{n-1}+2\times a_{n-2} +3\times a_{n-3} +b_{n_2} +2\times b_{n-3}$이다.

 

초항은 $a_1$, $a_2$, $a_3$ 각각 0, 1, 4이며, $b_0$, $b_1$, $b_2$는 각각 1, 1, 2이다.

MOD = 1_000_000_007
b = [1, 1, 2]
for i in range(1000):
    tmp = (b[-1] + b[-2] + b[-3])%MOD
    b.append(tmp)
a = [0, 0, 1, 4]
for i in range(4, 1001):
    tmp = (a[i-1] + 2*a[i-2] + 3*a[i-3] + b[i-2] + 2*b[i-3])%MOD
    a.append(tmp)

print(a[int(input())])