반응형
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()
반응형
'Problem Solving > BOJ' 카테고리의 다른 글
백준 14888번 연산자 끼워넣기 - 스위프트(Swift) 풀이 (0) | 2022.02.10 |
---|---|
백준 2581번 소수 - 스위프트(Swift) 풀이 (0) | 2022.02.10 |
백준 1022번 소용돌이 예쁘게 출력하기 - 스위프트(Swift) 풀이 (0) | 2022.02.09 |
백준 2568번 전깃줄 - 2 - 스위프트(Swift) 풀이 (0) | 2022.02.07 |
백준 2565번 전깃줄 - 스위프트(Swift) 풀이 (0) | 2022.02.07 |
댓글