코딩
[프로그래머스] 도둑질, 스티커모으기 .py 본문
programmers.co.kr/learn/courses/30/lessons/12971
programmers.co.kr/learn/courses/30/lessons/42897
def solution(sticker):
n = len(sticker)
if n <= 2:
return max(sticker)
dp1 = [sticker[0], sticker[0]]
dp2 = [0, sticker[1]]
for i in range(2, n):
dp2.append(max(dp2[i-2] + sticker[i], dp2[i-1]))
if i < n - 1:
dp1.append(max(dp1[i-2] + sticker[i], dp1[i-1]))
return max(dp1[-1], dp2[-1])
현재 index list[i]와 list[i-2]까지 더한 값 과 list[i-1]까지 더한 값을 비교하여 그 중 큰 값을 dp[i]에 저장.
dp[i] = max(dp[i-2] + list[i], dp[i-1])
이때, 리스트는 원형이므로 첫번째 index를 취하는 경우와 취하지않는 경우를 나누어준다.
1. 첫번째 index부터 시작할 경우 # 인접한 두번째 index는 계산할 수 없으므로 dp1[1]의 최댓값은 dp[0]이 된다.
dp1 = [list[0], list[0]]
2. 두번째부터 시작할 경우 # 첫번째는 계산하지 않으므로 dp[0]의 최댓값은 0 dp[1]의 최댓값은 list[1]이 된다.
dp2 = [0, list[1]]
'코딩테스트' 카테고리의 다른 글
[백준] 11055 가장 큰 증가 부분 수열 .py (0) | 2021.03.24 |
---|---|
[HackerRank] Lily's Homework .py (0) | 2021.03.04 |
파이썬 bisect_left, bisect_right 비교 (0) | 2021.02.24 |
[프로그래머스] 순위검색 .py (0) | 2021.02.23 |
[프로그래머스] 괄호변환 .py (0) | 2021.02.23 |
Comments