문제 링크 (opens new window)

풀이

1. 나머지 정리 활용하기, 오버플로우 발생
2. 점화식 제대로 세우기
3. 2xN 타일링 문제 2랑 거의 동일해서 헷갈렸는데, 2x2는 고려할 필요가 없었음.

import Foundation

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

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

print(dp[n])