BOJ-11726 2xn 타일링 Swift

문제

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

내가 푼 풀이

- n이 5일때까지 경우의 수를 구해봤는데 결국 피보나치 수열을 구하는 식이 나온다.

- f(n) = f(n-1) + f(n-2) 

- n이 일정숫자를 넘으면 담을수없이 커진다. 그래서 계산할때마다 10007로 나눈 나머지를 넣는다.

- f(n) % 10007 = ( f(n-1) + f(n-2) ) % 10007

 

import Foundation

var num = Int(String(readLine()!))!
var dp = Array(repeating: 0, count: 1001)
dp[1] = 1
dp[2] = 2
if num < 3 {
    print(dp[num])
} else {
    for i in 3...num {
        dp[i] = (dp[i-1] + dp[i-2]) % 10007
    }
    print(dp[num])
}