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

문제 설명

쉽게 말해 한 스티커를 뜯으면 양 옆의 스티커는 사용하지 못한다.

핵심은 스티커를 떼어내 최대 숫자를 구하는 것!

 

풀이

왜 dp인가?

이 문제를 보자마자 dp로 풀어야겠다고 생각했다.

근데 감만 온거지 왜 내가 dp로 풀겠다고 생각했는지..? 정확히 정의 내리기 어려웠다.

 

그래서 이번 기회에 dp 문제 구분법을 정의해봄

 

1. 수 많은 경우의 수가 있는가? -> 스티커를 뜯는 경우의 수가 매우 많음
2. 경우의 수중에 뭔가 반복적인 연산을 계속 하는가? -> 스티커 문제의 예시에서 14+11같이 계속 반복적인 연산을 한다

 

위의 2가지를 만족하면 dp문제라고 판단을 내렸다. (자세한 설명은 링크 참고)

 

 

 

 

풀이

이 문제는 dp를 두가지 경우로 나누어야 했다. (이부분은 생각해내지 못해 힌트를 보았다.)

 

1. 첫번째 스티커를 뗀 경우 -> 두번째 스티커는 사용하지 못함, dp[0] = sticker[0], dp[1] = sticker[0]

2. 첫번째 스티커를 떼지 않은 경우  -> dp[0] = 0, dp[1] = sticker[1]

 

위와 같이 두가지 케이스로 dp1, dp2를 나누어서 풀었다.

 

그리고 현재 스티커를 떼야 할지 말아야할지 바로 판단해야 한다. 
1. dp[i-2]+sticker[i] -> 현재 스티커를 뗀다.
2. dp[i-1]  -> 현재 스티커를 떼지 않는다.
둘 중 무엇이 더 큰지 판단하는

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

dp[i]를 구하는 코드이다.

 

전체 코드

func solution(_ sticker:[Int]) -> Int {
    // 스티커의 개수가 1개나 2개면 큰 수 리턴
    if sticker.count < 3 {
        return sticker.max()!
    }
    // 첫 번째 스티커를 떼었을 경우
    var dp1 = Array(repeating: 0, count: sticker.count)
    dp1[0] = sticker[0]
    dp1[1] = sticker[0]
    
    // 첫번째 스티커를 뗴지 않았을 경우
    var dp2 = Array(repeating: 0, count: sticker.count)
    dp2[0] = 0
    dp2[1] = sticker[1]
    
    for i in 2..<sticker.count {
        // 맨 마지막 스티커인 경우
        if i == sticker.count - 1 {
            dp2[i] = max(dp2[i-2]+sticker[i], dp2[i-1])
        } else {
            dp1[i] = max(dp1[i-2]+sticker[i], dp1[i-1])
            dp2[i] = max(dp2[i-2]+sticker[i], dp2[i-1])
        }
        
    }
    return max(dp1.max()!, dp2.max()!)
}

 

dp 어렵다..