코딩테스트 - 파이썬 - 스티커 수집 문제

def solution(sticker):
    n = len(sticker)

    if n <= 2:  # 스티커가 1개 또는 2개일 경우 가장 큰 값 반환
        return max(sticker)

    dp1 = [0] * n  # 0번 스티커부터 시작하는 경우
    dp1[0] = sticker[0]
    dp1[1] = max(sticker[0], sticker[1])
    for i in range(2, n-1):
        dp1[i] = max(dp1[i-1], dp1[i-2] + sticker[i])

    dp2 = [0] * n  # 1번 스티커부터 시작하는 경우
    dp2[n-1] = sticker[n-1]
    dp2[n-2] = max(sticker[n-1], sticker[n-2])
    for i in range(n-3, 0, -1):
        dp2[i] = max(dp2[i+1], dp2[i+2] + sticker[i])

    return max(dp1[n-2], dp2[1])  # 두 경우 중 가장 큰 값 반환

목표는 인접한 스티커를 수집할 수 없다는 제약 조건에 따라 스티커의 하위 집합을 수집하여 총점 값을 최대화하는 것

1. 스티커 목록의 길이가 2보다 작거나 같으면 최대 점수 값은 단순히 목록의 최대 요소입니다. 그렇지 않으면 함수는 두 개의 동적 프로그래밍 배열 'dp1' 및 'dp2'를 계산합니다.

2. 'dp1'은 마지막 스티커까지(포함하지 않음) 스티커를 모으면 얻을 수 있는 최대 포인트 값을 나타냅니다.

 

3. dp1의 처음 두 요소는 sticker의 처음 두 요소로 초기화되고 나머지 요소는 반복 관계 dp1[i] = max(dp1[i-1], dp1[i]를 사용하여 반복적으로 계산됩니다. -2] + 스티커[i]).

4. 'dp2'는 첫 번째 스티커부터(포함하지 않음) 스티커를 모을 때 얻을 수 있는 최대 포인트 값을 나타냅니다.

 

5. dp2의 마지막 2개 요소는 sticker의 마지막 2개 요소로 초기화되고 나머지 요소는 반복 관계 dp2[i] = max(dp2[i+1], dp2[i)를 사용하여 반복적으로 계산됩니다. +2] + 스티커[i]).

6. 마지막으로 최대 포인트 값은 dp1[n-2] 및 dp2[1]의 최대값이며, 여기서 n은 sticker의 길이입니다. -2 및 1 인덱스는 dp1의 마지막 요소가 끝에서 두 번째 스티커에 해당하고 dp2의 첫 번째 요소가 두 번째 스티커에 해당하기 때문에 사용됩니다.