728x90
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
분석
- 인접된 스티커 붙일 수 없음
- 첫번째 스티커 붙이냐 안붙이냐 두가지 DP 리스트 구하기
풀이
def solution(sticker):
if len(sticker) == 1:
return sticker[0]
dp = [0 for _ in range(len(sticker))]
dp[0] = sticker[0]
dp[1] = sticker[0]
for i in range(2, len(sticker) - 1):
dp[i] = max(dp[i-2] + sticker[i], dp[i-1])
dp2 = [0 for _ in range(len(sticker))]
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( max(dp), max(dp2))
728x90