[코딩테스트] 프로그래머스 - 스티커 모으기(2)

1. 아이디어 

▪ dp 알고리즘 사용

▪ 첫번째 스티커를 뗀 경우와 안 뗀 경우를 구분해서 해야함

   - why? 뗀 경우에 마지막 스티커는 사용할 수 없기 때문

▪ dp[i]를 i번째까지 스티커 배열에서 얻을 수 있는 최대 값이라고 한다면, 두가지 경우의 수로부터 dp[i]를 구할 수 있음

   - i-1번째 스티커를 뗀 경우 -> i번째 스티커는 뗄 수 없기 때문에 i-1번째까지의 최대값이 dp[i]가 됨

   - i-1번째 스키터를 떼지 않은 경우 -> i-2번째까지의 최대값 + i번째 스티커 값이 dp[i]가 됨

▪ 이를 점화식으로 나타내면 dp[i] = max(dp[i-1], dp[i-2] + sticker[i])

▪ 첫번째 스티커를 뗀 경우와 안 뗀 경우를 나눠서 dp 배열을 0부터 순서대로 채워주고, 배열의 마지막 값들 중 큰값 return

2. 시간복잡도

▪ O(N)

3. 변수

▪ 첫번째 스티커를 뗀 경우 dp 배열: int[]

▪ 첫번째 스티커를 안 뗀 경우 dp 배열: int[]

Code

def solution(sticker):
    if len(sticker) == 1:
        return sticker[0]
    
    # 첫번째 스티커를 뗀 경우
    dp1 = [0] * len(sticker)
    dp1[0] = sticker[0]
    dp1[1] = sticker[0]
    
    for i in range(2,len(sticker)-1):
        dp1[i] = max(dp1[i-1], dp1[i-2]+sticker[i])
    
    # 첫번째 스티커를 떼지 않은 경우
    dp2 = [0] * len(sticker)
    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])
    

    answer = max(dp1[-2],dp2[-1])
    
    return answer

프로그래머스