BOJ 1309 _ 동물원 _ 파이썬

📃 문제

백준 1309번 영역 구하기

알고리즘 - DP

💡 풀이 과정

우선 N에 대하여 결과 값을 세보아야 한다.
N=1 일때 1
N=2 일때 3
N=3 일때 17

격자판을 그리면서 규칙을 찾아보았다.

여기서 다음과 같이 규칙을 찾을 수 있다.

DP이기때문에 이전에 구해둔 최적해를 이용할 수 있는게 중요하다.
이를 직관적으로 볼 수 있게 빨간 화살표를 그려보았다.

한 행(즉, 두 칸)에서 일어날 수 있는 경우의 수는 세가지이다.
-> 없거나, 왼쪽이거나, 오른쪽
그리고 한행이 추가 될 때 일어날 수 있는 경우의 수는 두가지이다.
-> 바로 직전 행과 같을 수 없기 때문에 하나를 빼면 된다.

즉!
직전에 구해둔 경우에 한 행이 추가되는 경우를 생각할땐 직전에 구해둔 갯수 x2 !
그리고 그림에서 제일 아래칸 ((초록색화살표))의 경우를 생각해줘야 한다 !!
이 경우는 지금 추가되는행, 직전 행 두 행이 모두 비었을 경우이다. 이때는 두번째 전의 경우의 수만큼 발생 가능하다.

코드

그래서

dp[i] = (dp[i-2] + dp[i-1]*2)  (( i>=2)) 

로 생각할 수 있다 !

전체 코드

import sys
input = sys.stdin.readline

n = int(input())

dp = [0] * (n+1)
dp[0] , dp[1] = 1, 3

for i in range(2,n+1):
    dp[i] = (dp[i-2] + dp[i-1]*2) %9901

print(dp[n]%9901)```

N=1 일때 1
N=2 일때 3
N=3 일때 17
N=4 일때 41
까지 구해보고 여기서 방정식 규칙을 찾는 게 더 빠르긴 할것 같다 .. ^^^