[Python] 스티커 모으기(2)

코딩테스트 연습 - 스티커 모으기(2)

풀이

1. 첫 번째를 뜯거나 안뜯거나로 시작.

2. table[i]를 i번째 인덱스 까지의 얻을 수 있는 최댓값이라고 정의하면

    1) i-1 번째를 뗐을 경우 = i번째는 뗄 수 없다. i-1 번째 까지의 값 그대로

    2) i-1 번째를 떼지 않았을 경우 = i-2 번째 까지의 값, + sticker[i]

 

3. 초항은 

    1) i-1번째를 뗐을 경우 

        table[0], table[1] = sticker[0], table[0] 이고 마지막 인덱스 확인 안함 (2 ~ len(sticker) -1 )

    2) i-1번째를 뗐을 경우

        table[0], table[1] = 0, sticker[1] 이고 마지막 인덱스까지 확인

def solution(sticker):
    if len(sticker) == 1:
        return sticker[0]

    table1 = [0 for _ in range(len(sticker))]
    table1[0] = sticker[0]
    table1[1] = table1[0]
    for i in range(2, len(sticker) - 1):
        table1[i] = max(table1[i - 1], table1[i - 2] + sticker[i])
    value = max(table1)

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

    return max(value, max(table1))