2193번: 이친수

방법 1

문제 풀이 아이디어

이친수를 전체 하나로 보면 규칙성을 구하는 것이 쉽지 않습니다. 하지만 이친수의 특성을 생각해보면 0으로 끝나는 것과 1로 끝나는 것으로 나눌 수 있습니다.

즉 n 자리의 이친수를 구하기 위해 아래 2가지 방법을 사용할 수 있습니다.

1. 1로 끝나는 n의 자리 이친수는 n - 2 자리의 이친수에 01을 붙이는 방법으로 구할 수 있습니다.
2. 0으로 끝나는 n의 자리의 이친수는 n - 1 자리의 이친수에 0을 붙이는 방법으로 구할 수 있습니다.

코드

// 이친수
var cache = Array(repeating: -1, count: 91)

func f(_ n: Int) -> Int {
    if n == 1 || n == 2 {
        cache[n] = 1
    }
    
    if cache[n] < 0 {
        cache[n] = f(n - 2) + f(n - 1)
    }
    
    return cache[n]
}

print(f(Int(readLine()!)!))

방법 2

문제 풀이 아이디어

마찬가지로 이진수를 0으로 끝나는 수와 1로 끝나는 수로 나누어 봅니다. 이번에는 각각의 이진수의 수를 따로따로 구하는 방법입니다.

1. n 자리 0으로 끝나는 이진수는 0혹은 1로 끝나는 n - 1 자리의 이진수에 0을 붙이면 됩니다.
2. n 자리 1로 끝나는 이진수는 0으로 끝나는 n - 1 자리의 이진수에 1을 붙이면 됩니다.

코드

// 각각 0 혹은 1로 끝나는 n자리 이친수의 갯수
var zero = Array(repeating: -1, count: 91)
var one = Array(repeating: -1, count: 91)

func f0(_ n: Int) -> Int {
    if n == 1 {
        zero[n] = 0
    } else if n == 2 {
        zero[n] = 1
    }
    
    if zero[n] < 0 {
        zero[n] = f0(n - 1) + f1(n - 1)
    }
    
    return zero[n]
}

func f1(_ n: Int) -> Int {
    if n == 1 {
        one[n] = 1
    } else if n == 2 {
        one[n] = 0
    }
    
    if one[n] < 0 {
        one[n] = f0(n - 1)
    }
    
    return one[n]
}

let N = Int(readLine()!)!

print(f0(N) + f1(N))