BOJ-2133 타일 채우기 Swift

문제

3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자.

입력

첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다.

출력

첫째 줄에 경우의 수를 출력한다.

내가 푼 풀이

- 생각보다 많은 고민이 필요했던 문제다.

- 직접 그려보면서 확인한결과 N이 홀수일 때 주어진 크기의 타일로 절대 채울 수 없다.

- dp[n] = 3 x n 크기의 타일을 채우는 경우의 수라고 정해보자.

 

- dp[2] = 3

- dp[4] = dp[2] * 3 + 2 = 11

위 dp[2]를 이용한다면 dp[4] = dp[2] * 3 이 된다.

하지만 여기서 다른방식의 패턴이 나온다.

위와 같은 패턴이 크기가 4 이상인 타일에서 나온다.

위 두가지 패턴의 경우까지 합치면 dp[4] = dp[2] * 3 + 2 = 11이 된다.

 

- dp[6]

dp[6] 은 3 x 4 크기의 타일에서 2가 추가되었으므로

dp[4] * 3이 된다.

이는 4칸으로 가능한 모든 타일과 2칸이 추가되어서 2칸에서 만들 수 있는 타일의 경우의 수 3을 곱한 것이다.

또한 위 도형의 왼쪽 2칸을 채우는 경우의 수는 dp[2]이고 오른쪽의 4칸 타일의 경우의 수는 아래와 같다.

이 경우의 수는 dp[2] * 2로 나타낼 수 있다.

dp[6]에도 새로운 패턴의 타일이 있다.

위 세 가지 경우의 수를 합치면 dp[6] = dp[4] x 3 + dp[2] x 2 + 2가 된다.

 

위 경우의 수들을 종합하면 점화식은 다음과 같다.

dp[n] = dp[n-2] * 3 + (dp[n-4] * 2) + (dp[n-6] * 2) + .... + (dp[0] * 2) + 2 가된다.

 

코드로 구현해 보자.

import Foundation

var num = Int(readLine()!)!
var dp = Array(repeating: 0, count: 31)
// dp의 초기값 설정
// n이 홀수일때 주어진 타일로 채울 수 없다.
dp[0] = 0
dp[1] = 0
dp[2] = 3

// dp[n] = dp[n-2] * 3 + dp[n-4] * 2 + dp[n-6] * 2 + .... + dp[0] * 2 + 2
for i in stride(from: 4, through: 30, by: +2) {
    var sum = 0
    for j in stride(from: 0, through: i-4, by: +2) {
        sum += dp[j] * 2
    }
    dp[i] = dp[i-2] * 3 + 2 + sum
}

print(dp[num])