[Swift 알고리즘] 백준 BOJ - 9465 스티커

안녕하세요. 개발 중인 정주입니다.

 

오늘은 "백준 BOJ - 9465 스티커" 문제를 풀었습니다.

 

---

Github

GitHub - jeongju9216/SwiftAlgorithm: 스위프트 알고리즘

 

문제 링크

9465번: 스티커

 

---

풀이

이번 문제는 DP를 이용한 문제입니다.

초장부터 잘못 접근해서 결국에는 다른 분의 해설(https://yabmoons.tistory.com/523)을 보았습니다.

 

이번 문제의 핵심은 특정 위치의 스티커를 선택했을 때 얻을 수 있는 최대 점수를 저장하는 것입니다.

 

[ 50, 10, 100, 20, 40 ]

[ 30, 50, 70, 10, 60 ]

스티커가 위처럼 위치해 있을 때 1층 1번을 뗐을 때의 최대 점수, 2층 1번을 뗐을 때의 최대 점수 ... 2층 5번을 뗐을 때의 최대 점수를 기록합니다.

 

이 때, 1층 3번을 뗀 경우는 100 + max(2층 1번을 뗀 경우, 2층 2번을 뗀 경우)와 같습니다.

2층 3번을 뗀 경우는 70 + max(1층 1번을 뗀 경우, 1층 2번을 뗀 경우)와 같습니다.

 

기존의 값을 이용해 현재의 값을 구할 수 있으므로 DP로 풀 수 있는 것이죠.

 

마지막은 1층으로 시작한 경우와 2층으로 시작한 경우 중 최대 점수를 출력하면 됩니다.

 

---

전체 코드

//9465 스티커
import Foundation

let totalCount = Int(readLine()!)!
for _ in 0..<totalCount {
    let input = Int(readLine()!)!
    
    var table: [[Int]] = [[0], [0]]
    for i in 0..<2 {
        let scores = readLine()!.split(separator: " ").map { Int(String($0))! }
        table[i].append(contentsOf: scores)
    }
    
    var dp: [[Int]] = [[0, table[0][1]]
                      ,[0, table[1][1]]]
    if input >= 2 {
        for i in 2...input {
            dp[0].append(table[0][i] + max(dp[1][i-1], dp[1][i-2]))
            dp[1].append(table[1][i] + max(dp[0][i-1], dp[0][i-2]))
        }
    }
                     
    print(max(dp[0].last!, dp[1].last!))
}

---

아직은 초보 개발자입니다.

더 효율적인 코드 훈수 환영합니다!

공감과 댓글 부탁드립니다.