백준 9465번 스티커 - 스위프트(Swift) 풀이

1. dp(n, up, down) = n번째 열의 위아래 스티커 존재 여부가 up, down일 때, n번째 열부터 끝까지 고려했을 때 얻을 수 있는 최대 점수
2. n번째 열의 위아래 스티커 모두 떼지 않는 경우의 최대 점수 = dp(n+1, 1, 1)
3. n번째 열의 위 스티커만 떼는 경우의 최대 점수 = stickers[0][n] + dp(n+1, 0, 1)
4. n번째 열의 아래 스티커만 떼는 경우의 최대 점수 = stickers[1][n] + dp(n+1, 1, 0)
5. dp(n, up, down) = max(2번 경우, 3번 경우, 4번 경우)

---

1. dp(n, up, down) = n번째 열의 위아래 스티커 존재 여부가 up, down일 때, n번째 열부터 끝까지 고려했을 때 얻을 수 있는 최대 점수

 타일링 문제 시리즈와 비슷하다. 스티커를 하나 뗐을 때 영향을 미치는 곳은 상하좌우 1칸씩이고, 행이 2개뿐이다. 따라서 왼쪽 열부터 차례로 스티커를 뗄지 말지를 결정한다고 하면, 현재 열에 영향을 미치는 칸은 전 열의 두 칸뿐이다. 따라서 전 열의 두 칸의 상태를 알면, 현재 열에서 할 수 있는 액션을 결정할 수 있다.

 dp(n, up, down)을 n번째 열의 위아래 스티커 존재 여부가 각각 up, down일 때(1이면 존재, 0이면 존재하지 않음), n번째 열부터 끝열까지 고려했을 때 얻을 수 있는 최대 점수라고 두자. 최종적으로 구해야하는 것은 dp(0, 1, 1)이다.

 

2. n번째 열의 위아래 스티커 모두 떼지 않는 경우의 최대 점수 = dp(n+1, 1, 1)

  현재 열의 스티커를 모두 떼지 않으면 다음 열의 스티커는 무조건 두 개 다 남게 된다.(up=down=1) 따라서 이 경우 남은 부분에서 얻을 수 있는 최대 점수는 dp(n+1, 1, 1)이 된다.

 

3. n번째 열의 위 스티커만 떼는 경우의 최대 점수 = stickers[0][n] + dp(n+1, 0, 1)

 3, 4번의 경우는 모두 up, down을 고려해서 가능한 경우인지를 먼저 판단해야 한다. 위 스티커가 존재한다면(up = 1이라면), 이것을 떼는 경우를 고려할 수 있다. 스티커를 떼면서 해당 스티커의 점수를 얻고 stickers[0][n]는 동시에, 오른쪽 스티커가 찢어지기 때문에 dp(n+1, 0, 1)이 남은 부분에서 얻을 수 있는 최대 점수가 된다.

 

 

4. n번째 열의 아래 스티커만 떼는 경우의 최대 점수 = stickers[1][n] + dp(n+1, 1, 0)

 위의 경우와 비슷한 경우이다. 같은 방법으로 고려해주면 된다. 단, 이 경우 역시 아래 스티커가 존재하는 경우(down = 1)에만 고려해주어야 한다.

 

 

5. dp(n, up, down) = max(2번 경우, 3번 경우, 4번 경우)

위의 3가지 경우 중에서 최대값을 가지는 경우를 계산해서 해당 액션을 취하면 최대 점수를 얻게 된다.

 

---

import Foundation

var N = 0
var cache = Array(repeating: Array(repeating: Array(repeating: -1, count: 2), count: 2), count: 100001)
var stickers = Array(repeating: [Int](), count: 2)

// n번째 열의 위아래 스티커 존재 여부가 up, down일 때, n번째 열부터 끝까지 고려했을 때 얻을 수 있는 최대 점수
func dp(n: Int, up: Int, down: Int) -> Int {
    // 기저 사례
    if n == N { return 0 }
    
    // 캐싱
    var ret = cache[n][up][down]
    if ret != -1 { return ret }
    
    ret = dp(n: n + 1, up: 1, down: 1)                                  // 둘 다 그냥 두기

    if up == 1 {
        ret = max(ret, stickers[0][n] + dp(n: n+1, up: 0, down: 1))     // 위에거 떼기
    }
    if down == 1 {
        ret = max(ret, stickers[1][n] + dp(n: n+1, up: 1, down: 0))     // 아래거 떼기
    }
    
    cache[n][up][down] = ret
    
    return ret
}

func initTestcase() {
    cache = Array(repeating: Array(repeating: Array(repeating: -1, count: 2), count: 2), count: 100001)
}

func solution() -> String {
    var result = ""
    
    var T = Int(readLine()!)!
    while T > 0 {
        initTestcase()
        
        N = Int(readLine()!)!
        for i in 0..<2 {
            stickers[i] = readLine()!.split(separator: " ").map{ Int(String($0))! }
        }
        
        result.write("\(dp(n: 0, up: 1, down: 1))\n")
        
        T -= 1
    }
    
    return result
}

print(solution())