[프로그래머스] 스티커 모으기(2)

https://school.programmers.co.kr/learn/courses/30/lessons/12971

프로그래머스

 

접근

---

• 데이터 크기 10M → 웬만하면 O(n)으로 해결
• 숫자 몇 개를 더해 최대 합 구하기 → DP로 합 누적
• 원형으로 연결된 스티커 → DP 2개 활용
  • 0번째 인덱스가 포함인 경우, 0번째 인덱스를 포함하지 않는 경우
• x 인덱스를 택할 경우, x-1과 x+1인 양 옆은 사용할 수 없음
  • i에 대해서는 i-1 의 값을 더할 수 없지만, i-2 의 값은 더할 수 있음

 

코드

---

import Foundation

func solution(_ sticker:[Int]) -> Int{
    
    if sticker.count == 1{
        return sticker[0]
    }

    var dp = [Int](repeating: 0, count: sticker.count)
    var dp2 = [Int](repeating: 0, count: sticker.count)
    
    dp[0] = sticker[0]
    dp[1] = sticker[0]
    
    dp2[0] = 0
    dp2[1] = sticker[1]
    
    for i in stride(from: 2, to: sticker.count-1, by: +1){
        dp[i] = max(dp[i-2] + sticker[i], dp[i-1])
    }
    
    for i in stride(from: 2, to: sticker.count, by: +1){
        dp2[i] = max(dp2[i-2] + sticker[i], dp2[i-1])
    }
    
    return max(dp.max()!, dp2.max()!)
}