[백준/1309/파이썬] 동물원

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

1309번: 동물원

Problem

• 동물원 조련사의 머리가 아프지 않도록 우리가 2*N 배열에 사자를 배치하는 경우의 수가 몇 가지인지를 알아내는 프로그램을 작성해 주도록 하자.

조건

• 이 동물원에는 사자들이 살고 있는데 사자들을 우리에 가둘 때, 가로로도 세로로도 붙어 있게 배치할 수는 없다. 이 동물원 조련사는 사자들의 배치 문제 때문에 골머리를 앓고 있다.
• 사자를 한 마리도 배치하지 않는 경우도 하나의 경우의 수로 친다고 가정한다.

SOL

규칙성 발견하기

1부터 5까지 다 하고나서 알아낸 규칙입니다. 노가다 입니다. (진짜)

• F(n) = 2*F(n-1) + F(n-2) (n>=2) 
• 이런 문제는 적어도 1~5까지는 해보는 편

#bottom up
N = int(input())
DP= [1,3] + [0]*(N-1)
for i in range(2,N+1):
    DP[i] = (DP[i-2] + DP[i-1]*2)%9901
print(DP[N])

 

다른 시각으로 DP 스럽게 풀어보기

 

사자 우리는, 아무것도 없는 빈 우리로 끝나거나, 왼쪽철장에 사자가 있거나, 오른쪽 철장에 사자가 있는걸로 끝이난다.

그러므로, 3가지 상태의 이전 상태만 구해주면, 모든 경우의 수를 구하는게 된다.

 

정의

DP[n][0] = 빈 우리로 끝나는 경우

DP[n][1] = 왼쪽 철장에 사자가 있는 경우

DP[n][2] = 오른쪽 철장에 사자가 있는 경우

• 아무것도 없는 빈 우리로 끝나는 경우
  • 그 전의 우리도 비어있을 수 있다. DP[n-1][0]
  • 그 전의 우리는 왼쪽, 오른쪽에 모두 사자가 있을 수 있다. DP[n-1][1],DP[n-1][2]
• 왼쪽 철장에 사자가 있는 경우
  • 그 전의 우리는 비어있을 수 있다. DP[n-1][0]
  • 그 전의 우리에 오른쪽 철장에 사자가 있을 수 있다. DP[n-1][2]
• 오른쪽 철장에 사자가 있는 경우
  • 그 전의 우리는 비어있을 수 있다.DP[n-1][0]
  • 그 전의 우리는 왼쪽 철장에 사자가 있을 수 있다. DP[n-1][1]

점화식

DP[n][0] = DP[n-1][0] + DP[n-1][1]+DP[n-1][2]

DP[n][1] = DP[n-1][0] + DP[n-1][2]

DP[n][2] = DP[n-1][0] + DP[n-1][1]

 

#bottom up
import sys
input = sys.stdin.readline
N = int(input())
DP = [[0]*(3) for _ in range(N+1)]
#inital value
DP[1][0] = 1
DP[1][1] = 1
DP[1][2] = 1

for i in range(2, N + 1):
    DP[i][0] = (DP[i - 1][0] + DP[i - 1][1] + DP[i - 1][2]) % 9901
    DP[i][1] = (DP[i - 1][0] + DP[i - 1][2]) % 9901
    DP[i][2] = (DP[i - 1][0] + DP[i - 1][1]) % 9901

print(sum(DP[N]) % 9901)