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

문제 출처: 프로그래머스

프로그래머스

 

문제 설명

출처: 프로그래머스

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

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

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

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

스티커 모으기1 문제는 풀어보지 않았지만, 이와 비슷한 문제가 백준에서도 존재한다.

문제 유형 자체는 전형적인 DP 문제로 백준의 건물 색칠하기 문제와 유사하다.

 

문제에서 스티커가 원형이 아니었으면 하나의 DP배열을 이용해서 간단히 해결할 수 있지만, 원형이기 때문에 고려해야 할 사항이 추가된 셈이다.

 

<정답 코드>

def solution(sticker):
    n = len(sticker)
    if n == 1:
        return sticker[0]
    if n == 2:
        return max(sticker)
    
    dp1, dp2 = [0] * n, [0] * n
    dp1[0] = sticker[0]
    dp1[1] = max(sticker[0], sticker[1])

    dp2[1] = sticker[1]
    dp2[2] = max(sticker[1], sticker[2])

    for i in range(2, n):
        dp1[i] = max(dp1[i - 1], dp1[i - 2] + sticker[i]) if i < n-1 else dp1[i]
        dp2[i] = max(dp2[i - 1], dp2[i - 2] + sticker[i]) if 2 < i else dp2[i]

    return max(max(dp1), max(dp2))

접근 방법은 아래와 같다.

 

1. 0번 index의 스티커를 사용하는 배열 dp1, 사용하지 않는 배열 dp2를 생성한다.

    1-1. dp1배열은 마지막 스티커를 제외한 n-1개의 스티커를 사용하고, dp2는 0번 스티커를 제외한 n-1개의 스티커를                   사용한다.

2. 각 dp배열에서 처음 사용하게 되는 스티커는 sticker[i]로 초기화 해주고, 두번째로 사용하게 되는 스티커는 첫번째 스티       커와 비교해 더 큰 값으로 지정한다.

3. 앞의 스티커를 사용했을 경우, 바로 다음 스티커는 이용할 수 없으므로 dp[i-1]과 dp[i-2] + sticker[i]를 비교해 max값을      dp[i]에 삽입한다. (1-1을 어기지 않도록 작성한다.)

4. 두 배열 전체에서 가장 큰 값을 리턴한다.

 

3번의 부연 설명

dp[i]에서는 해당 스티커를 사용했을수도 사용하지 않았을 수도 있다.

- 사용했을 경우는 i+1번째 스티커를 사용할 수 없게 되므로 dp[i+1]은 dp[i-1]이 된다.

- 사용하지 않았을 경우는 dp[i-1]과 dp[i]가 같은 값이므로 dp[i-1]+sticker[i+1]이 dp[i-1]보다 클 수 밖에 없다. (조건에서 스티커의 value는 반드시 양수임을 보장하기 때문에)

 

비슷한 유형의 문제들을 많이 풀고 나니 이와 같은 문제들을 빠른 시간 안에 풀 수 있게 된 것 같다.