스티커 모으기 2

문제

---

https://programmers.co.kr/learn/courses/30/lessons/12971

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

 

 

나의 풀이

---

dp를 사용하면 되는 문제이다. 케이스는 두 가지이다. 첫 번째 스티커를 사용하는 경우와 사용하지 않는 경우이다. 따라서 dp1,dp2 두 개의 dp 배열을 만들어 저장하면 된다.

dp1의 경우 첫 번째 스티커를 사용하므로 dp1[0] = sticker[0], dp1[1] = dp1[0]이다. dp2의 경우 첫 번째 스티커를 사용하지 않으므로 dp2[0] = 0, dp2[1] = sticker[1]이다.

dp[i] = max(dp[i-1], dp[i-2]+sticker[i])의 식으로 dp를 갱신한 뒤 마지막에 max(max(dp1), max(dp2))를 return 해주면 된다.

 

코드

---

def solution(sticker):
    
    if len(sticker)==1:
        return sticker[0]
    
    dp1 = [0 for _ in range(len(sticker))]  # use first sticker
    dp2 = [0 for _ in range(len(sticker))]  # unuse first sticker
    
    dp1[0] = sticker[0]
    dp1[1] = dp1[0]
    
    dp2[1] = sticker[1]
    
    for i in range(2,len(sticker)-1):
        dp1[i] = max(dp1[i-1], dp1[i-2]+sticker[i])
    for i in range(2,len(sticker)):
        dp2[i] = max(dp2[i-1], dp2[i-2]+sticker[i])
    
    return max(max(dp1),max(dp2))