[백준/Swift] 2193번: 이친수

 

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

2193번: 이친수

 

 dp [1][i] = i자리가 1인 경우
 dp[0][i] = i자리가 0인 경우

    1 2 3 4 5 6
-----------------
0 | 0 1 1 2 3 5
1 | 1 0 1 1 2 3

개수를 세보면서 진행하면 규칙이 보인다!

dp[1][i]는 dp[0][i-1]의 값과 동일하고

dp[0][i]는 dp[0][i-1] + dp[1][i-1] 값이다!

 

//input
let n = Int(readLine()!)!
var dp = [[Int]](repeating: [Int](repeating: 0, count: n+2), count: 2)
dp[1][1] = 1
dp[0][1] = 0
if n > 1 {
    for i in 2...n {
        dp[0][i] = dp[0][i-1] + dp[1][i-1]
        dp[1][i] = dp[0][i-1]
    }
}
print(dp[0][n] + dp[1][n])