[백준 2193번] [Kotlin] 이친수

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

2193번: 이친수

 

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

 

 

설명

 

자리수 n에 따라 각 값을 하나씩 구해보면 규칙성을 찾을 수 있습니다.

 

n = 1

1

1개

 

n = 2

10

1개

 

n = 3

101 100

2개

 

n = 4

1000 1001 1010

3개

 

n = 5

10000 10001 10010 10100 10101

5개

 

n = 6

100000 100001 100010 100100 101000 101010 101001 100101

8개

 

즉, a[i] = a[i-1] + a[i-2] (a >= 3, a[1] = 1, a[2] = 1)과 같이 점화식을 구할 수 있습니다.

어디서 많이 본 점화식이죠?

피보나치 수열과 점화식이 동일하네요.

 

 

소스코드

fun main() {
    val br = System.`in`.bufferedReader()
    val n = br.readLine().toInt()
    val dp = Array(n + 1) { 0L }
    dp[1] = 1

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

위에서 구한 점화식을 그대로 소스코드로 구현하면 됩니다.

피보나치 수열과 점화식이 동일하기 때문에, 코드도 동일하네요.

 

 

 

후기

자리수 n에 따라 하나씩 값을 구하면서 규칙성을 찾아 풀 수 있는 문제였습니다.