[Swift 알고리즘] 백준 2133 타일 채우기

https://www.acmicpc.net/problem/2133

2133번: 타일 채우기

문제

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

입력

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

출력

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

n = 12일 때 예시

 

해결 방법

그림을 그려 점화식을 통하여 해결. 이러한 문제를 풀 때 새로운 모양을 앞이나 뒤에 붙이는 것으로 푼 적이 있다. 그렇게 된다면 좀 수월하게 풀리더라. 아래의 풀이과정의 경우 이전 DP값과, 인덱스에 존재하는 고유한 모양을 활용하여 계산한다. 

 

A(2)는 다음과 같다. A(2)의 경우 다음과 같이 3개의 모양이 나온다.

 

 

 

 

 

A(4)는 다음과 같다. A(4)의 경우 다음과 같은 모양이 나온다. 이전 A(2)를 활용하여 만든 모양과 A(4)일때 만들 수 있는 모양 2가지 따라서 A(4) = 11이다. 여기서 A2를 활용하지 않고 만든 새로운 2가지 모양을 newA(4)라고 하자.

 

A(4) = 11, newA(4) = 2

 

 

 

 

 

A(6)은 다음과 같다. 이전 DP값들을 적절하게 활용해서 하면 된다. 예를 들어 A(6)의 경우 [A(4)], [A(2)]를 활용하여 계산하면 가능하다. 

(1.) 이전에 구한 값인 A(4)를 왼쪽에 배치했다고 생각하자. 그러면 A(2)를 활용하여 계산하면 된다. A(4) * A(2) = 33. 

(2.) 그리고 생각할 것은 A(2)를 왼쪽에 배치했다고 생각하자. 무턱대고 A(4)를 곱해버리면 중복되는 수가 생겨버린다. 그러니까 A(2)를 배치하고 그 다음에 배치할 A(4)는  A(4)에서만 나타나는 newA(4)를 배치해야 한다. 이렇게 된다면 (1.)에서 계산한 값들과 겹치지 않는다. 왜냐하면 (1.)은 왼쪽에 A(4)를 배치했고, 어떤 숫자가 나와도 newA(4)가 오른쪽에 비치된 (2.) 와 전혀 다른 모양을 생성하기 때문이다.

(3.) A(6)에서 새로운 모양을 만든다.

A(6) = (1.) + (2.) + (3.)

(1.) A(4)와 A(2)를 활용한다.

 

 

(2.) A(2)와 newA(4)를 활용하여 만든다. 이렇게 된다면 (1.)과 (2.)는 전혀 다른 경우의 수를 만들 수 있다.

위에 그림들을 설명한 것이다.

 

 

A(8)의 경우도 마찬가지이다.

(1.) 이전에 만들었던 A(6)과 A(2)를 곱한다 

(2.) 기재된 그림과 같이 A(4)를 비치하고 newA(4) 와 곱을 계산한다.

(3.) A(2)를 비치하고 newA(6)와 곱을 계산한다.

(4.) newA(8)

 

 

 

 

 

 

A(10)의 경우도 다음과 같다.

 

 

예외처리 

홀수 일때는 계산이 안된다. 블록 하나으 너비가 2인데, 홀수일 경우는 Target 면적이 홀수가 된다. (3 * 홀수 = 홀수) 따라서 블록을 비치 할 수 없다.

 

코드 구현

func sol2133() {
    let inputN = Int(readLine()!)!

    var dpArr:[Int] = Array(repeating: 0, count: 31)
    dpArr[2] = 3
    dpArr[4] = 11
    if inputN <= 4{
        print(dpArr[inputN])
        return
    }
    var newArr = Array(repeating: 0, count: 31) //짝수일 때 새로 만드는 newA를 담는 함수.
    newArr[2] = 3
    for i in stride(from: 4, to: inputN + 1, by: 2) {
        newArr[i] = 2
    }
    
    for i in stride(from: 6, to: inputN + 1 + 1, by: 2) {
        for j in stride(from: i - 2, to: 2 - 1, by: -2) {
            dpArr[i] += dpArr[i - j] * newArr[j]
        }
        dpArr[i] += newArr[i]
    }
    print(dpArr[inputN])
}