프로그래머스 - 스티커 모으기(2)

https://programmers.co.kr/learn/courses/30/lessons/12971

접근

레벨4 답게 어려웠습니다.

처음에 생각한 방식은 여러가지 있었습니다.

1. DFS
2. 구간합

DFS의 경우 최대 깊이가 5만(최대길이 10만 / 2) 씩이나 되는 말도안되는 방식이라 아니라고 생각했고,
구간합도 구간의 합이 이전 스티커의 사용유무에 따라 달라지기 때문에 계산이 불가능하다고 생각했습니다.

아무리 생각해도 DP밖에 없어서 DP로 접근했습니다.

2차원 DP문제에 많이 익숙해서 인지 100,000 x 100,000배열을 선언할수 없어 고민을 오래한 문제였습니다.

결론은 1차원 DP를 사용하면 됐고, 레벨4인 이유는 앞의 스티커를 땠을 때, 때지 않았을때를 구분해서 2개의 경우를 고려해야 하기 때문이었습니다.

코드에서 dp[i]는 맨 앞 스티커를 사용하였다고 가정하고 2번째 스티커를 사용하지 않은 상태에서 i까지의 최대 값 입니다.

즉 dp[0]은 첫번째 스티커를 사용했기때문에 sticker[0]의 값과 같고,
dp[1]은 2번째 스티커를 사용하지 않았기 때문에 dp[0]과 값이 같아야 합니다.

이때 dp[2]부터 계산하면 dp[i] = max(dp[i-1](i번째 스티커를 사용하지 않은 최대값), dp[i-2]+sticker[i](i번째 스티커를 사용한 값))이 됩니다.

dp2는 첫번째 스티커를 사용하지 않은 경우 입니다.

두 배열 중 가장 높은 값을 return하면됩니다.

다음은 코드 전문입니다.

def solution(sticker):

    if len(sticker) == 1:
        return sticker[0]
    dp = [0 for _ in range(len(sticker))]  # use first sticker
    dp2 = [0 for _ in range(len(sticker))]  # unused first sticker

    dp[0] = sticker[0]
    dp[1] = sticker[0]

    dp2[0] = 0
    dp2[1] = sticker[1]

    for i in range(2, len(sticker) - 1):
        dp[i] = max(dp[i - 2] + sticker[i], dp[i - 1])

    value_1 = max(dp)

    for i in range(2, len(sticker)):
        dp2[i] = max(dp2[i - 2] + sticker[i], dp2[i - 1])
    value_2 = max(dp2)

    answer = max(value_1,value_2)
    return answer