[백준] 1904. 01타일 (Kotlin)

문제 : https://www.acmicpc.net/problem/1904

1904번: 01타일

지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이

www.acmicpc.net

풀이

// [백준] 1904. 01타일 (Kotlin)

import java.util.*

lateinit var dp : Array<Int>

fun main() = with(Scanner(System.`in`)){
    val n = nextInt()
    dp = Array(n+1){0}

    for(i in 0 .. n){
        find(i)
    }

    println(dp[n])
}

// 피보나치
fun find(n: Int){
    when(n){
        0-> dp[0] = 1
        1-> dp[1] = 1
        else-> {
            dp[n] = (dp[n-2] + dp[n-1]) % 15746
        }
    }
}

dp 문제로, 직접 n을 대입해보고 규칙성을 찾아서 풀었다.

n이 1 => 1 (1개)

n이 2 => 00,11 (2개)

n이 3 => 001, 100, 111 (3개)

n이 4 => 0000, 0011, 1100, 1001, 1111 (5개)

n이 5 => 00111, 10011, 11001, 11100, 00001, 10000, 00100, 11111 (8개)

피보나치 수열의 형태가 보인다.

따라서 점화식을

dp[n] = dp[n-2] + dp[n-1] 로 세워주었다.

하지만 피보나치 수는 46부터 int 범위를 초과하게 되는데, 출력조건에서 15746으로 나눈 나머지를 출력하라 했으므로

곱셉의 법칙을 생각해보면 dp값을 계산할때 다 15746의 나머지 처리를 해주면 된다는 것을 알 수 있다.