동물원

문제

어떤 동물원에 가로로 두칸 세로로 N칸인 아래와 같은 우리가 있다.

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

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

입력

첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다.

출력

첫째 줄에 사자를 배치하는 경우의 수를 9901로 나눈 나머지를 출력하여라.

예제 입력 1

예제 출력 1

풀이

문제를 이해해보자.

동물은 가로, 세로로 붙을 수 없다.
사자를 한 마리도 배치하지 않는 경우도 하나의 경우로 생각하자.

동물이 가로, 세로로 붙어있을 수 없다고 한다.

즉 대각선에 위치하거나 바로 전 후 가로, 세로 위치가 아닌 다른 인덱스에 위치해야 한다.

설계

경우의 수를 생각해보자.

2*n 크기의 배열이니 세가지 경우로 생각할 수 있다.

1️⃣ 동물이 왼쪽에 위치한 경우

index에 동물이 왼쪽에 위치했다면, index - 1은

오른쪽에 위치
왼쪽, 오른쪽 위치 x

2️⃣ 동물이 오른쪽에 위치한 경우

index에 동물이 오른쪽에 위치했다면, index - 1은

왼쪽에 위치
왼쪽, 오른쪽 위치 x

3️⃣ 동물이 위치하지 않은 경우

index에 동물이 위치하지 않았다면, index - 1은

왼쪽에 위치
오른쪽에 위치
왼쪽, 오른쪽 위치 x

=> 경우의 수를 생각해보니 규칙이 있는 것을 확인하였고 dp를 사용해 문제를 풀었다.

구현

왼쪽과 오른쪽, 그리고 위치하지 않은 경우도 생각해야하니 배열을 arr[N][3]으로 설정하였다.

arr[i][0] => 왼쪽인 경우
arr[i][1] => 오른쪽인 경우
arr[i][2] => 위치하지 않은 경우

위에서 설계한 규칙을 바탕으로 구현해보자.

1️⃣ 동물이 왼쪽에 위치한 경우

왼쪽에 위치한 경우 = 오른쪽에 위치한 경우 + 둘 다 위치하지 않은 경우

dp[i][0] = dp[i-1][1] + dp[i-1][2]

2️⃣ 동물이 오른쪽에 위치한 경우

오른쪽에 위치한 경우 = 왼쪽에 위치한 경우 + 둘 다 위치하지 않은 경우

dp[i][1] = dp[i-1][0] + dp[i-1][2]

3️⃣ 동물이 위치하지 않은 경우

둘 다 위치하지 않은 경우 = 왼쪽에 위치한 경우 + 오른쪽에 위치한 경우 + 둘 다 위치하지 않은 경우

dp[i][2] = dp[i-1][0] + dp[i-1][1] + dp[i-1][2]

전체코드

let N = Int(readLine()!)!
let mod = 9901

var dp = [[Int]](repeating: [Int](repeating: 0, count: 3), count: N)

dp[0][0] = 1
dp[0][1] = 1
dp[0][2] = 1

for i in 1..<N{
    dp[i][0] = dp[i-1][1] + dp[i-1][2]
    dp[i][1] = dp[i-1][0] + dp[i-1][2]
    dp[i][2] = dp[i-1][0] + dp[i-1][1] + dp[i-1][2]
    
    dp[i][0] %= mod
    dp[i][1] %= mod
    dp[i][2] %= mod
}

print(dp[N-1].reduce(0,+) % mod)