[백준/Swift] 9465번: 스티커

 

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

9465번: 스티커

 

i번째 열에서 1행 스티커를 선택한 경우, 2행 스티커를 선택한 경우를 나눠서 진행하면 된다. 상하좌우가 붙으면 안 되니까 한 열에 하나의 행만 선택하고, 이전 열 혹은 전전 열의 다른 행을 선택한 경우를 봐야 한다. 전전 열을 봐야 해서 맨 앞에 0을 추가하고 진행해 줬다. 아니면 1열의 전전 행은 -1 이니까... 맨 앞에 원소를 넣어서 1 열부터 스티커가 있다고 가정하고 시작하기.

dp[i][0] = 0행의 i열 스티커를 뗀 경우, dp[i][1] = 1행의 i열 스티커를 뗀 경우

A B C 

D E F

의 경우를 생각해보자!

dp[3][0] => C 스티커를 뗀 경우 -> A + E + C 혹은 D + C

여기서 왜 A + C가 안되냐면... 최댓값을 구해야 하기 때문에 A + C 가 아니라 A + E + C를 선택해야 됨!

dp에는 최댓값이 들어갔음을 보장하고 있기 때문에 dp를 사용해서 진행한다~

 n이 1인 경우를 꼭 처리해줘야 한다. 아니면 나처럼 99프로에서 런타임에러^^!

import Foundation

/*
 2행 n열
 뗀 스티커의 상하좌우 스티커 사용 불가
 점수의 합이 최대가 되도록 스티커를 떼어내려고 한다.
 */

//input
let t = Int(readLine()!)!
for _ in 0..<t {
    let n = Int(readLine()!)!
    var dp = [[Int]]()
    for _ in 0..<2 {
        dp.append(readLine()!.split(separator: " ").map{Int(String($0))!})
    }
    dp[0].insert(0, at: dp.startIndex)
    dp[1].insert(0, at: dp.startIndex)
    if n > 1 {
       for i in 2...n {
            dp[0][i] += max(dp[1][i-1], dp[1][i-2])
            dp[1][i] += max(dp[0][i-1], dp[0][i-2])
        }
    }
    print(max(dp[0][n], dp[1][n]))
}