[백준][KOTLIN] 1904 01타일

 

1904번: 01타일

풀이

• 문제의 규칙성을 찾는다.
  • N = 1 -> 1
  • N = 2 -> 2
  • N = 3 -> 3
  • N = 4 -> 5
  • N = 5 -> 8
• 위의 과정을 봤을 때 피보나치 수열의 규칙을 나타낸다.
• 각 2진 수열의 개수를 15746 값으로 나눈 나머지를 저장한다.

코드

import java.util.*

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    val n = sc.nextInt()
    val dp = IntArray(n + 1)
    dp[0] = 1
    dp[1] = 1

    for (i in 2..n) {
        dp[i] = dp[i - 1] + dp[i - 2]
    }

    println("${dp[n]}")
}