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

---

 

1. dp[index][first][second][third] = index번째 열의 각 행 상태가 first, second, third일 때, index열부터 남은 열을 모두 채우는 경우의 수
2. 현재 열의 상태에 따라 가능한 모든 경우의 수를 더한다.

 

1. dp[index][first][second][third] = index번째 열의 각 행 상태가 first, second, third일 때, index열부터 남은 열을 모두 채우는 경우의 수

 다이나믹 프로그래밍을 이용한다. dp[index][first][second][third]를 위와 같이 정의한다. first, second, third는 0일 때는 비어있음, 1일 때는 채워져 있음을 나타낸다. 최종적으로 구해야하는 것은 dp[0][0][0][0]이 된다.

 

2. 현재 열의 상태에 따라 가능한 모든 경우의 수를 더한다.

 현재 열을 모두 채우고 다음 열로 넘어가야 한다. 현재 열의 상태가 1, 0, 0인 경우, 아래와 같이 현재 열을 모두 채우는 경우는 2가지이다. 첫 번째 경우는 다음 열을 하나도 침범하지 않았으므로 dp(index+1, 0, 0, 0)의 경우의 수를 갖는다. 두 번째 경우는 다음 열의 second와 third를 침범하였으므로, dp(index+1, 0, 1, 1)의 경우의 수를 갖는다.

 

따라서 dp(index, 1, 0, 0) = dp(index+1, 0, 0, 0) + dp(index+1, 0, 1, 1)

 이렇게 현재 열의 상태에 따라 현재 열을 모두 채우는 경우를 다 고려해준다. 기저사례는 마지막 열까지 다 채우고 그다음으로 넘어갔을 때인 index = N이고, 이때 N번째 열은 비어있어야 마지막 열(N-1열)에서 밖으로 삐져나오지 않게 잘 채웠다는 의미이므로 first = second = third = 0인지 확인해주면 된다.

반응형

---

import Foundation

var N = 0
var cache = Array(repeating: Array(repeating: Array(repeating: Array(repeating: -1, count: 2), count: 2), count: 2), count: 31)

func dp(index: Int, first: Int, second: Int, third: Int) -> Int {
    if index == N { return first + second + third == 0 ? 1 : 0 }
    
    var ret = cache[index][first][second][third]
    if ret != -1 { return ret }
    
    switch first + second + third {
    case 3:
        ret = dp(index: index+1, first: 0, second: 0, third: 0)
    case 2:
        ret = dp(index: index+1, first: 1-first, second: 1-second, third: 1-third)
    case 1:
        if second == 1 {
            ret = dp(index: index+1, first: 1, second: 0, third: 1)
        } else {
            let case1 = dp(index: index+1, first: 1-first, second: 1-second, third: 1-third)
            let case2 = dp(index: index+1, first: 0, second: 0, third: 0)
            ret = case1 + case2
        }
    case 0:
        let case1 = dp(index: index+1, first: 1, second: 1, third: 1)
        let case2 = dp(index: index+1, first: 1, second: 0, third: 0)
        let case3 = dp(index: index+1, first: 0, second: 0, third: 1)
        ret = case1 + case2 + case3
    default: break
    }
    
    cache[index][first][second][third] = ret
    
    return ret
}

func solution() {
    N = Int(readLine()!)!
    
    print(dp(index: 0, first: 0, second: 0, third: 0))
}

solution()