BOJ-11727 2xN 타일링 2 Swift

문제

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

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

입력

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

출력

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

내가 푼 풀이

- n = 1 -> 1, n = 2 -> 3

- n = i 일때, 직사각형을 채울수 있는 방법은 3가지이다.

dp[i]는 2 x i 까지 채울수있는 직사각형의 경우의 수라고 한다면

 

1) i-1 까지 놓을 수 있는 경우의 수 + 2x1 타일을 놓는것 : dp[i-1]

i - 1

2x1

2) i-2 까지 놓을 수 있는 경우의 수 + 2x2 타일을 놓는것 : dp[i-2]

i - 2

2x2

3) i-2 까지 놓을 수 있는 경우의 수 + 2x2타일을 놓아 반으로 나눈 1x2타일 두개를 놓는것 : dp[i-2]

i - 2	1x2
	1x2

---> dp[i] = dp[i-1] + dp[i-2] + dp[i-2] 가 된다.

 

import Foundation

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

if count == 1 {
    print(dp[1])
} else {
    dp[2] = 3
    if count == 2 {
        print(dp[2])
    } else {
        for i in 3...count {
            dp[i] = (dp[i-1] + (2 * dp[i-2])) % 10007
        }
        print(dp[count])
    }
}