프로그래머스 스티커 모으기(2)
https://programmers.co.kr/learn/courses/30/lessons/12971
이전의 계산결과를 이용하는 dp를 사용하는 문제이다.
N이 10만이라는 점에서 완전탐색이나 dfs등의 방법을 사용한다면 시간초과의 가능성이 매우 커보였다.
그렇기 때문에 dp를 이용해 이전의 구간합을 구해주는 것이 문제인데,
이전값을 선택했는지 안했는지에 따라 dp값의 선택이 달라지는 문제가 있었다.
그렇기 때문에 dp를 2개를 생성하고 첫번째를 넣은 dp, 안넣은 dp로 나누어 계산하였다.
def solution(sticker):
if len(sticker) == 1:
return sticker[0]
dp = [0 for _ in range(len(sticker))] ## 앞의 스티커를 사용했다고 가정
value = 0
dp[0] = sticker[0]
dp[1] = dp[0]
for i in range(2,len(sticker)-1):
dp[i] = max(dp[i-2]+sticker[i], dp[i-1])
value = max(dp)
udp = [0 for _ in range(len(sticker))]
udp[0] = 0
udp[1] = sticker[1]
for i in range(2,len(sticker)):
udp[i] = max(udp[i-2]+sticker[i], udp[i-1])
value2 = max(udp)
return max(value,value2)
Author And Source
이 문제에 관하여(프로그래머스 스티커 모으기(2)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@wook2pp/프로그래머스-스티커-모으기2저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)