[백준] (Swift) 2193번 - 이친수 (스위프트 dp, 동적계획법, 2차원)

문제 링크

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

2193번: 이친수

 

풀이 IDEA

N=2 부터 규칙을 찾아보니까, 이전에 풀었던 동적계획법 문제와 비슷하게 끝자리에 따라서 경우가 나뉘었다. 아래와 같이 점화식을 도출할 수 있다.

 

이를 코드로 구현하면 아래와 같다. 

let n = Int(readLine()!)!
var dp = [[Int]](repeating: Array(repeating: 0, count: 2), count: n+1)

if n == 1 {
    print(1)
} else {
    dp[2][0] = 1
    dp[2][1] = 0

    for i in 3..<n+1 {
        dp[i][0] = dp[i-1][0] + dp[i-1][1]
        dp[i][1] = dp[i-1][0]
    }

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