[Swift 백준] 2193 이친수

 

풀이 아이디어

dp 문제입니다.

공통된 점화식을 찾아야합니다.

조건에 의하면 이친수는

 

• 무조건 1로 시작
• 11의 부분 문자열이 없어야함

입니다. 

 

n = 1 인 경우 [1] 으로 1개

n = 2 인 경우 [10] 으로 1개

n= 3 인 경우 [100, 101] 으로 2개

n = 4 인 경우 [1000, 1001, 1010] 으로 3개 입니다.

 

정확히 피보나치수와 같은 점화식을 갖고 있음을 알 수 있습니다.

 

 

풀이

let n = Int(readLine()!)!
var dp = Array(repeating: 0, count: 91)

dp[1] = 1
dp[2] = 1
dp[3] = 2

if n >= 4{
    for i in 4...n {
        dp[i] = dp[i-2] + dp[i-1]
    }
    print(dp[n])
} else {
    print(dp[n])
}