[백준 1904번] [Kotlin] 01타일

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

1904번: 01타일

 

난이도 : 실버 3
태그 : 다이나믹 프로그래밍

 

 

설명

다이나믹 프로그래밍에서 웰노운 문제들인 타일 시리즈.

이번엔 1과 00이라는, 조금 특이한 경우네요.

음... 어떻게 풀지 고민하다가, 결국 그냥 하나씩 써보면서 규칙성을 찾아보기로 했습니다.

 

 

n = 2

11

00

2개

 

n = 3

100

001

111

3개

 

n = 4

0000

0011

1100

1001

1111

5개

 

n = 5

00001

00100

10000

00111

11100

10011

11001

11111

8개

 

어라..? 피보나치 수열?

a(i) = a(i-1) + a(i-2)라는, 피보나치 수열과 동일한 점화식을 갖고 있었습니다.

점화식을 도출하는 과정이 어려울 뿐이지,

소스코드는 그냥 피보나치 수열을 구하면 되기 때문에 매우 간단할 것 같네요!

 

 

 

소스코드

fun main() {
    val n = readln().toInt()

    var n1 = 1
    var n2 = 2

    for (i in 0 until n - 2) {
        val temp = n1
        n1 = n2
        n2 = (temp + n2) % 15746
    }

    println(if (n == 1) 1 else n2)
}

 

 

 

후기

실버 3이라는 난이도는 점화식을 도출하는 과정이 어려워 붙은 것이지,

소스코드 자체는 그냥 피보나치 수열을 구하는 것이였기 때문에 생각보다 매우 간단했습니다.