[Swift 백준] 9465 스티커

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

 

풀이 아이디어 

일정한 규칙성이 있어서 dp로 풀이했습니다.

점화식은 아래와 같습니다.

 

• dp[0][i] = max(dp[1][i-1], dp[1][i-2]) + board[0][i]
• dp[1][i] = max(dp[0][i-1], dp[0][i-2]) + board[1][i]

n이 1인 경우등도 잘 신경써줍니다(한번 틀림..)

자세한 풀이는 아래와 같습니다.

 

풀이

let t = Int(readLine()!)!

for _ in 0..<t {
    let n = Int(readLine()!)!
    var board = [[Int]]()
    for _ in 0..<2 {
        let input = readLine()!.split(separator: " ").map { Int($0)! }
        board.append(input)
    }

    var dp = Array(repeating: Array(repeating: 0, count: n), count: 2)

    dp[0][0] = board[0][0]
    dp[1][0] = board[1][0]

    if n == 1 {
        print(max(dp[0][0], dp[1][0]))
        continue
    }

    dp[0][1] = board[0][1] + dp[1][0]
    dp[1][1] = board[1][1] + dp[0][0]

    for i in 2..<n {
        dp[0][i] = max(dp[1][i - 1], dp[1][i - 2]) + board[0][i]
        dp[1][i] = max(dp[0][i - 1], dp[0][i - 2]) + board[1][i]
    }

    print(max(dp[0][n - 1], dp[1][n - 1]))
}