백준 1309 [kotlin]

문제

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

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

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

입력

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

출력

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

풀이

dp[i][j] 배열을 만든다.

i는 0 1 2로 0은 왼쪽에 사자 1은 오른쪽 사자 2는 사자를 놓지 않은 경우이다.

j는 N번째 배열에 경우의 수이다.

 

dp[0][N] 은 왼쪽에 사자를 넣는 경우이므로 dp[1][N-1] 과 dp[2][N-1] 로 N-1번째의 오른쪽과 놓지 않은 경우의 수를 더해준다

dp[1][N]은 오른쪽에 사자를 넣는 경우이므로 dp[0][N-1]과 dp[2][N-1] 로 N-1번쨰의 왼쪽과 놓지 않은 경우의 수를 더해준다

dp[2][N]은 안놓는 경우이므로 N-1번째의 모든 경우의 수를 더해준다.

 

추가적으로 우리의 크기가 100000이므로 경우의 수는 long long 배열을 넘어서므로 매번 경우의 수를 계산할 때마다 9901로 나누어주고 

입력받은 N번째의 경우의 수를 구할때도 최대 9900 + 9900 + 9900 으로 넘어서므로 9901로 또 나누어준다.

코드

fun main()
{
    val N = readLine()!!.toInt()
    val dp = Array(3, {IntArray(100001,{0})})
    dp[0][0] = 1
    dp[1][0] = 1
    dp[2][0] = 1
    for(i in 1..100000)
    {
        dp[0][i] = (dp[2][i-1] + dp[1][i-1]) % 9901
        dp[1][i] = (dp[2][i-1] + dp[0][i-1]) % 9901
        dp[2][i] = (dp[0][i-1] + dp[1][i-1] + dp[2][i-1]) % 9901
    }
    println((dp[0][N-1] + dp[1][N-1] + dp[2][N-1]) % 9901)
}