[백준] 1309번 : 동물원 (Python)

문제 : https://www.acmicpc.net/problem/1309

 

 

이 문제는 가로로도 세로로도 붙어있지 않게,

2*N 배열에 사자를 배치하는 경우의 수를 구하는 문제다.

 

import sys

input = sys.stdin.readline

N = int(input()) # 우리의 크기
DP = [1]*(N+1)
MOD = 9901

# DP 채우기
DP[1] = 3

for n in range(2, N+1):

    DP[n] = (2*DP[n-1]+DP[n-2])%MOD

# 답 출력
print(DP[N]%MOD)

 

 

 

[문제풀이]

---

 

n-1 경우의 수에 2를 곱하고, n-2 경우의 수를 더한 값이 현재 사자를 배치할 수 있는 경우의 수!