ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [Programmers] 스티커 모으기(2)
    Algorithm/Programmers 2021. 10. 9. 13:21

    출처: 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])
    }

     

    배운점

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

    기초는 튼튼 꾸준히!!

    댓글

Designed by Tistory.