[Programmers] 스티커 모으기(2)

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

분류: dp

 

---

접근

배열의 길이도 100,000 으로 크고 이 스티커를 뗄지 안 뗄지, 앞에껄 땠는지 안 땠는지 등등의 경우를 고려해줘야 하니 DP로 문제로 접근을 했어요.

 

그냥 배열의 첫 번째를 기준으로 잡으면,

이 스티커를 땔 경우 DP vs 떼지 않을 경우 DP 

두 번의 DP를 구해서 최대를 구하면 되는 문제였네요

 

처음에 저도 이렇게 접근은 했는데 첫 번째 인덱스부터 DP, 마지막 인덱스부터 거꾸로 DP 라는 엉뚱한 풀이로 해서.. 

꽤나 삽질을 했습니다 😰

 

풀이

일단 각 케이스의 0, 1번 기저 사례를 구해주고 2번 인덱스부터 점화식으로 적용해주면 됩니다.

(사실 n이 3일 때는 하나밖에 땔 수 없으니 3까지는 셋 중에 제일 큰 값이 최대입니다.)

 

첫 번째 스티커를 뗄 경우 

이땐 마지막 스티커를 뗄 수는 없으니 n-1 번째까지 가야합니다.

기저 사례를 생각하면,

그리고 0번 인덱스에서 최대는 당연히 sticker[0]가 될테고,

1번 스티커를 뗄 수 없으니 1번 스티커의 최대도 sticker[0]이 됩니다.

 

첫 번째 스티커를 떼지 않을 경우

이때의 기저 사례는 1번 인덱스에 sticker[1]을 넣어주면 되겠네요 :)

 

점화식은 k번째 스티커를 떼는 게 좋을지 안 떼는 게 좋을지 결정해야 합니다.

스티커를 뗀다고 하면 k-1은 쓸 수가 없으니,

DP[k-2] + sticker[k] 가 최적이겠네요!

떼지 않을 때는, DP[k-1]이 최적의 경우일거에요,

둘 중 큰 값을 비교해주면 되겠네요 ;)

 

점화식은 아래와 같이 되겠죠!

DP[k] = max(DP[k-2] + sticker[k], DP[k-1])

 

import Foundation

func solution(_ sticker:[Int]) -> Int {
    let n = sticker.count
    
    guard n > 3 else { 
        return sticker.max()!
    }
    
    var dp1 = [Int](repeating: 0, count: n)
    var dp2 = [Int](repeating: 0, count: n)
    
    dp1[0] = sticker[0]
    dp1[1] = sticker[0]
    for idx in 2..<n-1 {
        dp1[idx] = max(dp1[idx-2] + sticker[idx], dp1[idx-1])
    }
    
    dp2[1] = sticker[1]
    for idx in 2..<n {
        dp2[idx] = max(dp2[idx-2] + sticker[idx], dp2[idx-1])
    }
    
    return max(dp1[n-2], dp2[n-1])
}

 

배운점

오랜만에 푸니 또 감을 잃은 것 같다.. 

기초는 튼튼 꾸준히!!