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

🏝 문제 설명

 

 

N개의 스티커가 원형으로 연결되어 있습니다. 다음 그림은 N = 8인 경우의 예시입니다.

원형으로 연결된 스티커에서 몇 장의 스티커를 뜯어내어 뜯어낸 스티커에 적힌 숫자의 합이 최대가 되도록 하고 싶습니다. 단 스티커 한 장을 뜯어내면 양쪽으로 인접해있는 스티커는 찢어져서 사용할 수 없게 됩니다.

 

예를 들어 위 그림에서 14가 적힌 스티커를 뜯으면 인접해있는 10, 6이 적힌 스티커는 사용할 수 없습니다. 스티커에 적힌 숫자가 배열 형태로 주어질 때, 스티커를 뜯어내어 얻을 수 있는 숫자의 합의 최댓값을 return 하는 solution 함수를 완성해 주세요. 원형의 스티커 모양을 위해 배열의 첫 번째 원소와 마지막 원소가 서로 연결되어 있다고 간주합니다.

---

제한 사항

• sticker는 원형으로 연결된 스티커의 각 칸에 적힌 숫자가 순서대로 들어있는 배열로, 길이(N)는 1 이상 100,000 이하입니다.
• sticker의 각 원소는 스티커의 각 칸에 적힌 숫자이며, 각 칸에 적힌 숫자는 1 이상 100 이하의 자연수입니다.
• 원형의 스티커 모양을 위해 sticker 배열의 첫 번째 원소와 마지막 원소가 서로 연결되어있다고 간주합니다.

---

입출력 예

[14, 6, 5, 11, 3, 9, 2, 10]	36
[1, 3, 2, 5, 4]	8

---

입출력 예 설명

 

입출력 예 #1
6, 11, 9, 10이 적힌 스티커를 떼어 냈을 때 36으로 최대가 됩니다.

 

입출력 예 #2
3, 5가 적힌 스티커를 떼어 냈을 때 8로 최대가 됩니다.

---

 

🏝 풀이 코드

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, 6, 5, 11, 3, 9, 2, 10] 배열을 가지고 어떻게 선택을 해야 좋을 지 생각해보자.

이 배열을 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]가 된다.

 

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

각 배열의 사이즈를 하나씩 늘려가면서 '새로 들어온 수'를 기준으로 들었다.

그리고 [14, 6, 5, 11]에서 보았듯이, 11을 선택했다고 해서 바로 5를 제외한 앞의 값인 6을 선택한 것이 아니라, 14를 선택했다.

기존 배열에서는 점화식을 찾기 어렵지만, DP 배열에서는 조금 보일 수 있다.

 

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]을 추가해주었다. 점화식이 덧셈 연산이라 결과에 영향을 미치지도 않고 구현도 편리하게 도와주는 스킬이었다.

 

- 원형 DP를 푸는 방법

1. 원형 조건을 제거한 상태에서 DP의 점화식 이끌기

2. 원형 조건은 2가지 케이스로 분리해서 DP 연산을 각 케이스마다 돌리고 결과 반영

 

2022.10.14 - [🐍 코딩테스트 대비 : PS] - [프로그래머스] 도둑질 (level4, python)

[프로그래머스] 도둑질 (level4, python)

 

위 문제와 완전히 동일하며, 풀이코드 역시 동일하다. 한 번 더 연습이 필요하다면 이 문제로 복습하는 것도 좋다.