코테 노트/프로그래머스

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

화요밍 2021. 7. 27. 02:03
728x90
반응형

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

 

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

N개의 스티커가 원형으로 연결되어 있습니다. 다음 그림은 N = 8인 경우의 예시입니다. 원형으로 연결된 스티커에서 몇 장의 스티커를 뜯어내어 뜯어낸 스티커에 적힌 숫자의 합이 최대가 되도록

programmers.co.kr

 

최종 코드

 

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

프로그래머스 알고리즘 소스 코드 모음. Contribute to hwayeon351/Programmers-Algorithms development by creating an account on GitHub.

github.com

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)

 

 

728x90
반응형

'코테 노트 > 프로그래머스' 카테고리의 다른 글

Level 3 하노이의 탑 Python3  (0) 2021.07.29
Level 3 최고의 집합 Python 3  (0) 2021.07.29
Level 3 멀리 뛰기 Python 3  (0) 2021.07.27
Level 3 거스름돈 Python 3  (0) 2021.07.26
Level 3 기지국 설치 Python 3  (0) 2021.07.25