[백준] 동물원 (1309)(kotlin)

문제 설명

백준 1309번 문제 링크

입력 및 출력

» 입력

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

» 출력

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

예제 입출력(테스트케이스)

입력	출력
4	41

문제 풀이1

풀이 참고

import java.util.Arrays

fun main() = with(System.`in`.bufferedReader()) {
    val N = readLine().toInt()
    val dp = Array(N + 1) { IntArray(3) }
    Arrays.fill(dp[1], 1)
    for (i in 2..N) {
        dp[i][0] = dp[i - 1][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][0] %= 9901
        dp[i][1] %= 9901
        dp[i][2] %= 9901
    }

    println(dp[N].reduce { acc, i -> acc + i } % 9901)
}

문제 풀이2

풀이 참고

fun main() = with(System.`in`.bufferedReader()) {
    val N = readLine().toInt()
    val dp = IntArray(N + 1)
    dp[0] = 1
    dp[1] = 3
    for (i in 2..N) {
        dp[i] = (dp[i - 1] * 2 + dp[i - 2]) % 9901
    }
    println(dp[N])
}

시뮬레이션(점화식)