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

박형진·2022년 2월 23일
0

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


1. 전체 코드

def solution(sticker):
    if len(sticker) <= 3:
        return max(sticker)
    if len(sticker) == 4:
        return max(sticker[0] + sticker[2], sticker[1] + sticker[3])
    
    # 첫 번째 스티커를 뽑는 경우
    dp = [0] * len(sticker)
    dp[0] = sticker[0]
    dp[1] = sticker[0]
    # 첫 번째 스티커를 뽑을 경우 마지막 스티커 사용 불가이므로 탐색 범위 -1
    for i in range(2, len(sticker) - 1):
        dp[i] = max(dp[i - 1], sticker[i] + dp[i - 2])
    a = dp[-2]
    
    # 첫 번째 스티커를 뽑지 않는 경우( != 무조건 두 번째 스티커를 뽑는 경우)
    dp = [0] * len(sticker)
    dp[0] = 0
    dp[1] = sticker[1]
    for i in range(2, len(sticker)):
        dp[i] = max(dp[i - 1], sticker[i] + dp[i - 2])
    b = dp[-1]
    return max(a, b)


print(solution([14, 6, 5, 11, 3, 9, 2, 10]))

2. 후기

    dp[i] = max(dp[i - 1], sticker[i] + dp[i - 2])

다이나믹 프로그래밍 문제를 풀 때, 자주 볼수있는 점화식 형태이다. 이 문제가 어려웠던 점은 점화식은 금방 떠올렸는데 첫 번째 스티커를 뽑는 처리가 복잡하다고 생각했다. 그래서 단순하게 두 가지 경우를 모두 계산했다.

초기 풀이에서는 첫 번째 스티커를 뽑지 않는다는 것을 두 번째 카드만을 뽑는 경우로 한정지어서 풀었는데 당연히 오답처리를 받았다.

0 또는 제거된 스티커의 값을 대입해주면서 제거한 것과 같은 효과를 가지게 했고, range의 범위를 조절하여 마지막 스티커는 탐색하지 않는 방법을 사용하여 문제를 풀었다.

profile
안녕하세요!

0개의 댓글