[프로그래머스] 스티커 모으기2

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

프로그래머스

🤔 문제분석

첫번째 스티커를 붙힌경우, 첫번째 스티커를 붙히지 않은경우(마지막 스티커를 붙힌경우) 두 가지 중 가장 큰 값을 찾아서 리턴하면 된다.

다이나믹 프로그래밍을 활용해야 하는데 또한 2가지 사항에 대하여 고려해야한다.

1. 현재위치에서 스티커를 붙히는 경우 i-2 번째에서의 최대값 + 현재 스티커 값
2. 현재위치에서 스티커를 붙히지 않는 경우 i-1 번재에서의 최대값

1번과 2번 사항 중 최대값으로 갱신 해 나아가면 된다.

💻 코드

# 첫번째 스티커를 땐 경우
# 첫번째 스티커를 때지 않은경우 중 최대값
def solution(sticker):
    n = len(sticker)
    if n == 1:
        return sticker[-1]

    first_dp = [0] * n
    last_dp = [0] * n

    first_dp[0] = sticker[0]
    # 1번스티커을 붙힌경우 2번스티커를 붙힌경우중 최대값
    first_dp[1] = max(sticker[0], sticker[1])
    # 2번 스티커를 붙힌게 최대값이다 ( 1번 스티커를 붙히지 않는경우라고 가정하기때문 )
    last_dp[1] = sticker[1]
    for i in range(2, n):
        if i == n - 1:
            last_dp[i] = last_dp[i-2] + sticker[i]
            first_dp[i] = first_dp[i-1]
        else:
            first_dp[i] = max(first_dp[i - 2] + sticker[i], first_dp[i - 1])
            last_dp[i] = max(last_dp[i-2] + sticker[i], last_dp[i-1])

    return max(last_dp[-1], first_dp[-1])