[Kotlin] 백준(BOJ) 2193 이친수

문제 전문은 아래 버튼을 눌러 확인하실  수 있습니다.

문제

0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다.

1. 이친수는 0으로 시작하지 않는다.
2. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.

예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되므로 이친수가 아니다.

N(1 ≤ N ≤ 90)이 주어졌을 때, N자리 이친수의 개수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 N이 주어진다.

 

출력

첫째 줄에 N자리 이친수의 개수를 출력한다.

 

예제 입출력

 

문제 해설

이친수는 다음과 같이 정의할 수 있다. 

 

이진수이다.

 

첫 자리는 반드시 $1$이다. 

 

$1$은 연속될 수 없다. 

 

뒤에서 부터 생각해봤을 때, 끝자리는 $0, 1$ 둘다 올 수 있다.

 

$dp[n][0]$: 길이가 $n$이고 마지막이 $0$인 이친수의 경우의 수

$dp[n][1]$: 길이가 $n$이고 마지막이 $1$인 이친수의 경우의 수 

라고 정의했을 때, 

 

마지막이 $0$인 경우

이전 자리는 $0, 1$ 둘다 올 수 있으므로 다음과 같이 나타낼 수 있다. 

$dp[n][0] = dp[n-1][0] + dp[n-1][1]$

 

마지막이 $1$인 경우

$1$은 연속될 수 없으며, 이전 자리는 $0$이어야 하므로 다음과 같이 나타낼 수 있다.

$dp[n][1] = dp[n-1][0]$

 

결론적으로 점화식은 다음과 같이 나타낼 수 있다. 

$dp[n][0] + dp[n][1] = dp[n-1][0] + dp[n-1][1] + dp[n-1][0]$

 

기저값 구하기

$dp[1][1]$의 경우에는 $1$인 경우밖에 없으므로 경우의 수는 $1$가지이다

$dp[1][0]$의 경우에는 애초에 존재하지 않으므로 $0$가지이다. 

 

위 내용들을 바탕으로 다음과 같이 구현할 수 있다.

소스 코드

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

    val dp = Array(n + 1) { LongArray(2) }

    dp[1][1] = 1  // "1"

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

    println(dp[n][0] + dp[n][1])
}

 

 

시간 복잡도

for문 내부에서 상수번 연산을 수행하므로 $O(N)$ 시간 복잡도를 가진다고 할 수 있겠다.