백준 - 이친수 (2193)

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

for i in stride(from: 2, through: N, by: 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])

어떤 이친수가 0으로 끝나면 그 뒤의 수로 0과 1이 둘 다 올 수 있다. 1로 끝나면 0만 올 수 있다.

이 아이디어를 사용해서 점화식을 다음과 같이 도출할 수 있다.

dp[i][0] = dp[i - 1][0] + dp[i - 1][1]]
dp[i][1] = dp[i - 1][0]

길이가 i이고 끝이 0인 이친수의 개수는 길이가 i-1이고 끝이 0인 이친수와 길이가 i-1이고 1인 이친수의 개수의 합과 같다.

길이가 i이고 끝이 1인 이친수의 개수는 길이가 i-1이고 끝이 0인 이친수의 개수와 같다.