백준 - 2xn 타일링 (11726)

let MOD = 10007
let n = Int(readLine()!)!
var dp = Array(repeating: 0, count: n + 1)

dp[1] = 1
if n > 1 {
    dp[2] = 2
}

for i in stride(from: 3, through: n, by: 1) {
    dp[i] = (dp[i - 1] + dp[i - 2]) % 10007
}

print(dp[n])

길이가 N인 타일을 채우는 경우는 N - 1까지 채워져 있는 상황에서 2 1 타일을 채우는 경우와 N - 2까지 채워져 있는 상황에서 2 2 타일을 채우는 경우로 나뉜다.

따라서 점화식은 dp[i] = dp[i - 1] + dp[i - 2] 로 도출할 수 있다.