문제 링크 (opens new window)

풀이

1. 나머지 정리 활용하기, 오버플로우 발생
2. 점화식 제대로 세우기

import Foundation

let n = Int(readLine()!)!
var dp: [Int] = .init(repeating: 0, count: 1004)

dp[1] = 1
dp[2] = 3
if n < 3 {
    print(dp[n])
    exit(0)
}
for i in 3...n {
    dp[i] = ((dp[i-1] % 10007) + (2 * dp[i-2]) % 10007) % 10007
}

print(dp[n])