✅Lv3. 스티커 모으기

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

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

 

#1. 개선할 점

 

- 해당 문제는 n이 10만이므로 완전탐색을 수행하기에는 시간복잡도가 너무 컸다.

따라서 dp를 생각했지만, dp 점화식을 세우지 못했다.

 

이전 스티커의 dp 값으로 다음 스티커 값을 도출하려고 했지만,

다음 스티커 값이 0이 포함되면 안되는 마지막 스티커일 경우에

이전 스티커의 값에 0번째 스티커가 선택되는 경우가 포함되면 안되는데, 그 경우를 모두 생각해서 식을 세울 수 없었다.

 

-> 모든 경우를 생각해서 식을 세울 수 없다면, 경우를 나누자.

 

case = 1) 첫번째 스티커를 떼는 경우 -> 마지막 스티커는 계산하지 않는다.
case = 2) 첫번째 스티커를 떼지 않는 경우 -> 마지막 스티커까지 계산한다.
-> case 1, 2의 최댓값을 리턴한다.

 

 

dp[i]는 i번째까지 탐색했을 때 얻을 수 있는 최댓값으로,

i번째 스티커가 떼질 경우 또는 떼지지 않을 경우까지 고려하여 최댓값을 설정해야하므로

다음과 같은 점화식을 세울 수 있다.

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

 

처음에는 이전 스티커값이 최댓값이면 실제 값이 사라지는 게 아닌가? 하고 이해가 안됐었는데,

어차피 다음 스티커는 무조건 2번째 이전의 스티커만 선택할 수 있는게 아니라 -3, -4, ... 까지

바로 전 스티커만 아니면 다 선택할 수 있으므로 매번 최댓값을 구하는 다음식이 성립한다는 것을 알 수 있었다.

 

 

#2. 설계 및 풀이

 

def solution(sticker):
    if len(sticker) == 1 :
        return sticker[0]
    if len(sticker) == 2 :
        return max(sticker)
    
    dp1 = [0] * len(sticker) # 첫번째 스티커를 떼는 경우
    dp2 = [0] * len(sticker) # 첫번째 스티커를 떼지 않는 경우
    
    #1. 첫번째 스티커를 떼는 경우
    dp1[0] = sticker[0]
    dp1[1] = dp1[0] ## 주의!! 첫번째 스티커를 떼면 두번째는 뗄 수 없음
    for i in range(2, len(sticker)-1) :
        dp1[i] = max(dp1[i-1], dp1[i-2] + sticker[i])
        
    #2. 첫번째 스티커를 떼지 않는 경우
    dp2[0] = 0
    dp2[1] = sticker[1]
    for i in range(2, len(sticker)) :
        dp2[i] = max(dp2[i-1], dp2[i-2] + sticker[i])
        
    return max(dp1[len(sticker)-2], dp2[len(sticker)-1])

 

 

#3. 배운 점

 

- 길이가 10만정도인 배열을 다뤄야하는 문제는 완탐으로 해결 안될 경우 dp를 먼저 생각해보자.

 

- 특정 조건때문에 dp 점화식이 한번에 안세워지면 특정 조건을 기준으로 문제를 나눠서 점화식을 세워보자.

 

- 점화식을 세울 때 dp[i]가 뭘 뜻하는 지 기준을 잘 세우자.

 

예를 들어 dp[i]가 i번째 스티커를 뗐을 때의 최댓값을 의미한다면,

점화식은 dp[i] = max(dp[0], ... ,dp[i-4], dp[i-3], dp[i-2]) + dp[i]가 될 것이다.

이 경우는 시간복잡도가 거의 완전탐색과 동일하므로 점화식으로 적절하지 않다.

 

따라서 dp[i]를 i번째까지 탐색했을 때 얻을 수 있는 최댓값으로 기준을 설정하면

위와같은 문제를 해결할 수 있다.