Level 3 스티커 모으기(2) Python 3

https://programmers.co.kr/learn/courses/30/lessons/12971?language=python3 

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

 

최종 코드

• GitHub -> https://github.com/hwayeon351/Programmers-Algorithms/blob/main/level3_스티커모으기(2).py

GitHub - hwayeon351/Programmers-Algorithms: 프로그래머스 알고리즘 소스 코드 모음

def solution(sticker):
    if len(sticker) == 1: return sticker[0]
    dp1 = [0]*len(sticker)
    dp2 = [0]*len(sticker)
    
    #첫번째 뽑는 경우
    dp1[0] = sticker[0]
    dp1[1] = sticker[0]
    for i in range(2, len(sticker)-1):
        dp1[i] = max(dp1[i-2]+sticker[i], dp1[i-1])
    
    #두번째 뽑는 경우
    dp2[0] = 0
    dp2[1] = sticker[1]
    for i in range(2, len(sticker)):
        dp2[i] = max(dp2[i-2]+sticker[i], dp2[i-1])

    return max(dp1[len(sticker)-2], dp2[len(sticker)-1])

---

풀이 과정

def solution(sticker):
	#스티커가 1개인 경우, 해당 스티커에 적혀있는 숫자가 최댓값
    if len(sticker) == 1: return sticker[0]
    
    #dq[i] = i번째 스티커까지 뜯은 스티커에 적혀있는 숫자의 합을 저장 -> 메모이제이션
    #dp1 -> 첫번째 스티커를 뜯는 경우
    #dp2 -> 두번째 스티커를 뜯는 경우
    dp1 = [0]*len(sticker)
    dp2 = [0]*len(sticker)
    
    #첫번째 스티커를 뜯는 경우, 마지막 스티커는 뜯을 수 없다
    dp1[0] = sticker[0]
    dp1[1] = sticker[0]
    for i in range(2, len(sticker)-1):
    	#dp1[i-2]+sticker[i] = i번째 스티커를 뜯는 경우
        #dp1[i-1] = i번째 스티커를 뜯지 않는 경우
        dp1[i] = max(dp1[i-2]+sticker[i], dp1[i-1])
    
    #두번째 스티커를 뜯는 경우, 마지막 스티커를 뜯을 수 있다
    dp2[0] = 0
    dp2[1] = sticker[1]
    for i in range(2, len(sticker)):
      	#dp2[i-2]+sticker[i] = i번째 스티커를 뜯는 경우
        #dp2[i-1] = i번째 스티커를 뜯지 않는 경우  
        dp2[i] = max(dp2[i-2]+sticker[i], dp2[i-1])

    return max(dp1[len(sticker)-2], dp2[len(sticker)-1])
#시간복잡도 = O(n), 공간복잡도 = O(n)