Programmers / 3단계 / 스티커 모으기(2) / python

 

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

 

 

나의 풀이 (테스트 실패)

def solution(sticker):
    num1 = 0
    num2 = 0
    maxN = 0
    
    if len(sticker) == 1:
        return "".join(sticker)
    
    if len(sticker) % 2 == 1:
        for i in range(0, len(sticker)-1, 2):
            num1 += sticker[i]
    else:   
        for i in range(0, len(sticker), 2):
            num1 += sticker[i]

    for j in range(1, len(sticker), 2):
        num2 += sticker[j]
        
    if num1 > num2:
        maxN = num1
    else:
        maxN = num2
    return maxN

 

모범 답안

def solution(sticker):
    answer = 0
    if len(sticker) == 1:
        return sticker.pop()

    size = len(sticker)
    # 1번 선택하는 경우 -> 1..n-1번 배열에 대한 DP
    dp1 = [0] + sticker[:-1]
    for i in range(2, size):
        dp1[i] = max(dp1[i-1], dp1[i-2] + dp1[i])
    
    # 2번 선택하는 경우 -> 2...n번 배열에 대한 DP
    dp2 = [0] + sticker[1:]
    for i in range(2, size):
        dp2[i] = max(dp2[i-1], dp2[i-2] + dp2[i])
        
    answer = max(dp1[-1], dp2[-1])
    return answer

 

DP에 대한 문제였다.

각 자리마다 해당 위치까지의 최적의 해를 저장한다.

 

[14]만 주어진 배열이라면, 14를 선택하는 것이 최적이다.

[14, 6]이 주어진 배열인 경우, 새로 들어온 6을 선택하면 14를 선택하지 못한다. 14가 더 크므로 14를 선택하는 것이 최적이다, 따라서 DP배열은 [14, 6] → [14, 14]로 변화한다.

 

기존 배열 [14, 6, 5]의 경우를 보자. 새로 들어온 5를 선택하게 되면, 6은 선택하지 못하지만, 앞의 14는 선택이 가능하다. 5를 선택하지 않고 6을 선택하면 14도 선택하지 못하므로, 19 > 6이므로 19를 선택하는 것이 최적이다. 따라서 DP 배열은 [14, 14, 5]→[14, 14, 19]이다. 기존 배열 [14, 6, 5, 11]의 경우, 새로 들어온 11을 선택하게 되면 5는 선택하지 못하지만, 6이나 14를 선택할 수 있다. 여기서 6을 선택하게 되면 14를 선택하지 못하니, 11 + 14를 하는 것이 더 옳다. 14 + 5의 조합보다 더 크므로, 25가 선택되는 것이 옳다. 따라서DP 배열은 [14, 14, 19, 11] → [14, 14, 19, 25]가 된다.

 

여기서 점화식을 이끌어 낼 수 있다. 

DP배열에서 DP[i] = max(DP[i] + DP[i-2], DP[i-1])이라는 식을 이끌 수 있는데, 이를 해석하면 다음과 같다.

DP[i] = 최댓값(새로 들어온 수 + 2칸 전까지의 최적의 값, 1칸 전의 최적의 값)

 

하지만, 여기서 원형이라는 조건이 있다. 0번 인덱스의 스티커를 떼면 -1번 인덱스의 스티커는 사용하지 못하는 것이다.

따라서 두 가지의 경우로 분리해서 생각해보자.

1) 0번 인덱스의 스티커를 떼는 경우

2) 1번 인덱스의 스티커를 떼는 경우

 

1번은, 마지막 인덱스의 스티커는 무조건 사용하지 못한다. 따라서 마지막 요소를 제거한 [:-1] 범위에 대해서 DP를 한 번 돌린다.

2번은, 0번 인덱스의 스티커는 무조건 사용하지 못한다. 따라서 가장 앞 요소를 제거한 [1:] 범위에 대해서 DP를 한 번 돌린다.

각 경우의 최댓값들 중 최댓값이 정답이 된다.

 

또한 점화식 자체가 i-2까지 나오기 때문에 주어진 배열의 인덱스 에러가 나지 않도록 주의하여야 한다.

원활한 계산을 위해 [:-1]배열과 [1:] 배열 모두 앞에 [0]을 추가해주었다. 점화식이 덧셈 연산이라 결과에 영향을 미치지도 않고 구현도 편리하게 도와준다.

 

 

참조

https://hoons-dev.tistory.com/84

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