백준 2718번 타일 채우기 - 스위프트(Swift) 풀이 + 그림 설명

---

 

1. dp(n, state) = n번째 열의 상태가 state일 때, n번째 열부터 마지막 열까지 채우는 방법의 수
2. state는 n열의 1~4행의 상태를 비트마스크로 나타낸 것이고, 0~16 중 하나의 값을 갖는다.
3. dp(n, state) = ∑ dp(n+1, 주어진 state에서 만들 수 있는 다음 열의 상태)

 

1. dp(n, state) = n번째 열의 상태가 state일 때, n번째 열부터 마지막 열까지 채우는 방법의 수

 왼쪽 열부터 차례로 채워나간다. 최종적으로 구해야 하는 것은 dp(1, 0)이다.

 

2. state는 n열의 1~4행의 상태를 비트마스크로 나타낸 것이고, 0~16 중 하나의 값을 갖는다.

 n번째 열을 채우려면 n-1번째 열을 채우면서 n번째 열이 어떤 상태가 되었는지 알아야 한다. 타일을 가로로 놓으면 다음 열을 침범하기 때문이다. 아래 코드에서는 아래행(4행)부터 오른쪽 비트에 대응되도록 하였다.

 

3. dp(n, state) = ∑ dp(n+1, 주어진 state에서 만들 수 있는 다음 열의 상태)

일단 n번째 열을 꽉 채워야 하기 때문에 주어진 state에서 빈 곳을 다 채우는 모든 경우의 수를 고려해준다. 아래 그림처럼 state = 8(1000)인 경우를 예로 들어보자.

 

 비어있는 1, 3, 4행을 채워야 한다. 이 행들을 모두 채우는 경우의 수는 아래와 같이 3가지이고, 각각 다음 열의 상태를 1, 4, 7로 바꾼다. 따라서 dp(n, 8) = dp(n+1, 1) + dp(n+1, 4) + dp(n+1, 7)이다.

 

 재귀 호출의 기저 사례는 n = N + 1일 때, 즉 모든 열을 다 채웠을 때이고, 이때 삐져나온 것이 없어야 하므로 state가 0이어야 채우기에 성공한 것이다.

반응형

---

import Foundation

var N = 0
var cache = [[Int]]()

func dp(n: Int, state: Int) -> Int {
    if n == N + 1 { return state == 0 ? 1 : 0 }
    
    var ret = cache[n][state]
    if ret != -1 { return ret }
    
    let next: [Int]
    switch state {
    case 0: next = [0, 3, 9, 12, 15]
    case 1: next = [2, 8, 14]
    case 2: next = [1, 13]
    case 3: next = [0, 12]
    case 4: next = [8, 11]
    case 5: next = [10]
    case 6: next = [9]
    case 7: next = [8]
    case 8: next = [1, 4, 7]
    case 9: next = [0, 6]
    case 10: next = [5]
    case 11: next = [4]
    case 12: next = [0, 3]
    case 13: next = [2]
    case 14: next = [1]
    case 15: next = [0]
    default:
        next = []
    }
    
    ret = 0
    next.forEach{ ret += dp(n: n+1, state: $0) }
     
    cache[n][state] = ret
    
    return ret
}

func initTestcase() {
    cache = Array(repeating: Array(repeating: -1, count: 16), count: 1001)
}

func solution() {
    var resultString = ""
    var T = Int(readLine()!)!
    
    while T > 0 {
        initTestcase()
        
        N = Int(readLine()!)!
        
        resultString.write("\(dp(n: 1, state: 0))\n")
        
        T -= 1
    }
    
    print(resultString)
}

solution()