728x90
반응형
https://programmers.co.kr/learn/courses/30/lessons/12971?language=python3
최종 코드
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 |