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

 

Problem

 

코딩테스트 연습 - 스티커 모으기(2)

---

Solution

해당 문제는 DP(Dynamic Programming)으로 풀어야 하는 문제입니다.

 

1. 스티커의 갯수가 3개 이하라면 가장 큰 수를 반환한다.

 

스티커의 갯수가 3개 이하라면 하나밖에 뗄 수 없으므로 가장 큰 수를 반환합니다.

 

if sticker.count < 4 { return sticker.max()!}

 

2. 첫 번째 스티커를 뜯어냈을 경우와 두 번째 스티커를 뜯어냈을 경우의 dp를 만들어줍니다.

 

 var dp1:[Int] = [sticker[0],sticker[0]]
 var dp2:[Int] = [0,sticker[1]]

 

3. 이전에 쌓인 합을 이용해 더 좋은 스티커를 뜯어냅니다.

 

더 좋은 스티커를 뜯어내기 위한 식은 max(dp[i-2] + sticker[i] 와 dp[i-1]) 입니다.

 

이유는 스티커를 뜯어낼 수 있는 조건은 현재 위치에서 2칸 앞 스티커와 3칸 앞 스티커입니다.

 

만약 [14, 6, 5, 11, 3, 9, 2, 10] 이렇게 있다고 가정하고 0번째 스티커인 14를 뜯어냈을 때

 

2칸 앞 스티커는 5와 3칸 앞 스티커는 11입니다.

 

5와 11 중 당연히 11이 좋다고 생각할 수 있지만 만약 11옆에 1000이라는 숫자가 있었다면 어떻게 될까요?

 

11을 뜯어냄으로써 1000을 잃게 될 것입니다.

 

고로 5를 뜯어내고 그 다음 1000을 더했을 때와 11을 뜯어내고 그 다음 숫자를 뜯어냈을 떄 이렇게 2수 앞을 내다봐야 합니다.

 

고로 위와 같은 식이 성립되는 것이죠.

 

for i in 2..<sticker.count {
        dp1.append(max(dp1[i-2]+sticker[i],dp1[i-1]))
        dp2.append(max(dp2[i-2]+sticker[i],dp2[i-1]))
    }

 

4. 첫 번째 스티커를 뜯어냈을 때 가장 마지막 값을 삭제해준다.

 

첫 번째 스티커를 뜯어냈을 땐 가장 마지막 스티커도 뜯어지므로 마지막 값을 삭제해줍니다.

 

dp1.removeLast()

 

5. 가장 큰 값을 반환한다.

 

첫 번째 스티커를 뜯어냈을 때와 두 번째 스티커를 뜯어냈을 때의 값들 중 가장 큰 값을 반환합니다.

 

return max(dp1.max()!,dp2.max()!)

---

Source Code

 

---

느낀점

 

난 역시 다이나믹 프로그래밍에 너무 약하다...

 

어떻게 풀어야할지도 감이 안왔고... 결국 다른 사람 풀이를 봤는데 풀이를 봐도 이해하는데 좀 시간이 걸렸다...

 

시간 남을 때 다이나믹 프로그래밍만 빡세게 준비해야겠다..

 

아 그리고 이 문제가 원래 4단계였는데 3단계로 내려온거 같다... 다른 분들을 다 4단계라고 하셨네..

 

어쩐지 어렵더라..