1309 - 동물원

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

1309번: 동물원

[문제 요약]

동물원에 가로로 두칸 세로로 N칸인 우리가 존재한다.

이 동물원에는 사자들이 살고 있다. 사자들을 조건에 맞게 우리에 배치하자.

 

[조건]

사자들은 가로나 세로로 붙어 있게 배치할 수 없다.

 

[문제 풀이]

사자들은 가로나 세로로 붙어 있게 배치할 수 없기 때문에 대각선으로 배치되거나 옆에 배치되지 않는 방식으로 우리가 구성되어야 합니다.

저는 다이나믹 프로그래밍 방법으로 문제를 해결하였습니다.

 

1. 사자는 하나의 줄로 존재할 수 없다. 따라서 왼쪽에만 존재하거나, 오른쪽에만 존재하거나 해당 줄에 한마리도 존재하지 않는 경우로 줄마다 3개의 경우가 존재한다.

2. N의 길이만큼 for문을 돌며 각각의 경우의 수를 갱신한다.

 

3. 만약 n의 길이가 2라고 생각해보자. 사자를 하나만 놓게되는 경우가 생긴다면 그것은 왼쪽에만 사자가 있거나 오른쪽에만 사자가 있는 경우이다. 다른 경우로 이전 우리에서 양쪽에 사자가 아예 없었다면 어느쪽이든 존재할 수 있다. 

 

규칙이 보이기 시작한다.

현재 우리에서 사자가 있는 우리와 없는 우리로 분리한 뒤빈 우리의 수 × 3 + 사자가 있는 우리 × 2 를 하면 되는 것이다.

 

공식으로 풀어보자면,

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

해당 공식으로 구성해서 해결해 보았다.

 

import sys
input = sys.stdin.readline

n = int(input())
dp = [[0,0,0] for _ in range(n+1)]

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)