[백준] 01타일 (1904)(kotlin)

문제 설명

백준 1904번 문제 링크

입력 및 출력

» 입력

첫 번째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 1,000,000)

» 출력

첫 번째 줄에 지원이가 만들 수 있는 길이가 N인 모든 2진 수열의 개수를 15746으로 나눈 나머지를 출력한다.

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

입력	출력
4	5

문제 풀이1

풀이참고

var N = 0
var dp = intArrayOf()

fun main(args: Array<String>) = with(System.`in`.bufferedReader()) {
    N = readLine().toInt()
    dp = IntArray(N + 2) { -1 }

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

    println(fibo(N))
}

fun fibo(tile: Int): Int {
    if (dp[tile] == -1) {
        dp[tile] = (fibo(tile - 1) + fibo(tile - 2)) % 15_746
    }

    return dp[tile]
}