[Algorithm/Swift] 프로그래머스(Lv.3) - 스티커 모으기(2)

안녕하세요 제인입니다! 

오늘은 <프로그래머스(Lv.3) - 스티커 모으기(2)> 문제 풀이를 통해 dp 유형 풀이 과정을 정리해보도록 하겠습니다.

해당 문제를 풀면서 대표적인 dp 유형이라고 생각이 들어 정리해두면 좋을 것 같아서 가져왔습니다!

문제 링크

프로그래머스

문제 풀이

처음 접근

저는 처음에 투포인터로 접근을 했었는데요,, 다른 풀이를 참고해서 dp로 해결한 후 생각해보니까 dp로 풀 수 밖에 없는 문제라는 생각이 드는 것 같습니다..! 처음에 투포인터로 접근한 이유는 start, end 포인터 모두 0에 두고 시작해서 처음으로 떼는 스티커의 인덱스에 start 포인터를 두고 end 포인터 변수를 2씩 늘려가면서(인접 인덱스의 스티커는 떼지 못하기 때문) 체크해주면 될 것 같다고 생각해서 였습니다. 이 과정을 start가 0인 경우, 1인 경우(첫번째 스티커를 떼느냐, 두번째 스티커를 떼느냐) 두 번 체크해서 비교해주면 된다고 생각했는데!! 풀고 나서 생각해보니까 하나 건너 하나씩 떼는 경우만 체크해주면 확인 못하게 되는 케이스([1, 100, 1, 1, 100] 이런 식으로 주어지는 경우 )가 생길 수 있겠더라구요.. 그래서 다른 블로그들의 풀이를 참고해서 dp 알고리즘을 활용해서 최종적으로 풀이해주었습니다!

DP를 활용한 풀이 과정

dp 문제는 dp 유형인지만 잘 파악하면(네 이게 어렵지만요) 점화식만 잘 세우면 결과 값을 도출해낼 수 있습니다!

점화식을 세우기 위해서는 규칙을 잘 파악하면 되겠죠??

이 문제에서 찾을 수 있는 규칙은, 일단 첫번째 스티커를 뜯었을 경우와 뜯지 않았을 경우 이렇게 두 가지 케이스로 나뉜다는 것입니다.

그렇기 때문에 뜯은 스티커에 적힌 숫자들의 합을 저장할 배열을 두 개 만들어 줍니다. (dp1, dp2)

이 두 배열의 크기는 sticker 배열의 크기와 같고 인덱스에는 지금까지 뜯은 스티커에 적힌 숫자들의 합이 저장되고, (메모이제이션 기법) 가장 마지막에 뜯은 스티커의 인덱스에 최종 값이 저장되게 됩니다. 

 

첫번째 스티커를 뜯은 경우(dp1), sticker[0] 자리의 스티커를 뜯은 것이기 때문에 dp1[0]에 sticker[0] 값을 저장해주고, 바로 옆 스티커인 dp1[1]은 뜯지 못하는 스티커이기 때문에 똑같이 sticker[0]의 값을 저장해줍니다.

첫번째 스티커를 뜯지 않은 경우(dp2), 두번째 자리의 스티커를 뜯을 수 있기 때문에 dp[1]에 일단 sticker[1]을 저장해줍니다.

 

그 다음, for 문을 이용해 가능한 범위(첫번째를 뜯은 경우는 마지막 스티커 못뜯기 때문에 n-2번째 인덱스까지)까지 검사해줍니다.

dp[i] = max(dp[i-2] + sticker[i], dp[i-1])

 

for문에서 이용하게 되는 점화식은 i번째 스티커를 떼는 것이 좋을지 아닐지 결정하는 과정으로, 위와 같습니다. 

i번째 스티커를 뗄 경우, i-1번째 스티커는 떼지 못하므로 dp[i-2] + sticker[i]가 최적이 되고,

떼지 않을 경우는 dp[i-1]이 최적이 되는 것이기 때문에 dp[i]에 저장되는 값(= 누적 합의 최댓값)으로 dp[i-2] + sticker[i] 와 dp[i-1] 중 큰 값을 골라주면 되는 것입니다.

Swift 풀이 코드

import Foundation

func solution(_ sticker:[Int]) -> Int{  
    let n = sticker.count
    
    if n <= 2 {
        return sticker.max()!
    }
  
    var dp1 = Array(repeating: 0, count: n)
    var dp2 = Array(repeating: 0, count: n)
  
    // 첫번째 스티커를 뜯었을 경우
    dp1[0] = sticker[0]
    dp1[1] = sticker[0]
  
    // 첫번째 스티커를 뜯지 않았을 경우
    dp2[0] = 0
    dp2[1] = sticker[1]
  
    for i in 2..<n {
        dp2[i] = max(dp2[i-2] + sticker[i], dp2[i-1])
    
        if i < n - 1 {
        dp1[i] = max(dp1[i-2] + sticker[i], dp1[i-1])
        }
    }
  
    return max(dp1[n-2], dp2[n-1])
}

---

[참고 자료]

프로그래머스: 스티커 모으기(2) - Swift