Summer/Winter Coding - # 10. 스티커 모으기(2)

코딩 테스트 연습 - 스티커 모으기(2) | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

• 스티커 모으기(2)

문제 설명

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

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

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

제한 사항

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

---

입출력 예stickeranswer

[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로 최대가 됩니다.

---

[문제 해설]

0. 스티커를 찢으면 해당 값의 양쪽은 쓸 수 없게 된다. 그럼 한 칸을 뛰어서 최댓값을 찾는 dp문제는 많이 보셨을 거다.

1. 쉽게 max(dp [i - 1], dp[i - 2] + stiker [i]) 를 떠올릴 수 있을지도?

2. 맹점은 이문제는 원형이라는 점이다.

3. 그렇다면? 어떻게 해야 할까? 여러 방법을 풀 수 있겠지만 2가지 케이스를 나눠서 푸는 게 제일 좋을 듯싶다.

a, b, c, d, e, f 가 원형으로 돼있다면

첫 케이스는 a, b, c, d, e 만의 탐색으로 최댓값을 찾는 것이다. 

f는 왜 안 찾는가? 아시다시피 한쪽을 쓰면 양쪽을 쓸 수 없다. 때문에 미리 한쪽은 쓸 수 없다고 가정하는 것!

f를 안 씀으로써 a b, c, d, e는 원형이 아니라 선형으로 볼 수 있게 되는 것입니다.

즉, 한칸만 뛰우기만 하면 조건을 충족하게 된다.

두 번째 케이스는 a를 스킵하고 b, c, d, e, f에서 최댓값을 찾는 것. 이전과 원리는 같다.

f를 쓸 경우 a는 쓸 수 없게 되므로 이점을 착안하는 것. a를 안 쓰면 마찬가지로 b ~ f의 선형 리스트가 되는 것이다.

 

4. 읽고 나서 바로 이해가 안 가실 수 있다. 다만 a, b, c, d, e, f가 원형이 돼있으므로 이점을 선형으로 바꾸는 작업이 필요하다 혹은 원형 그대로의 모습으로 최대값을 찾는 로직이 필요하겠다.

5. 원형 로직을 찾는 공식은 어려울 거 같아서 우회법으로 푸는 것.

 

---

[코드]

 

def solution(sticker):
    answer = 0
    
    if len(sticker) == 1:
        return sticker[0]
    
    cycle = len(sticker)
    dp1 = [0 for _ in range(len(sticker))]
    dp1[0] = sticker[0]
    
    for i in range(1, len(sticker) - 1):
        dp1[i] = max(dp1[i - 1], dp1[i - 2] + sticker[i])
    
    # 두 계산
    dp2 = [0 for _ in range(len(sticker))]
    for j in range(1, len(sticker)):
        dp2[j] = max(dp2[j - 1], dp2[j - 2] + sticker[j])
    
    max1 = dp1[-2]
    max2 = dp2[-1]
    # print(dp1, dp2)
    answer = max(max1, max2)
    return answer

 

---

후기

 

원형을 바로 풀려고 하지 말고,

돌아가는 방법

즉 선형으로 만드는 법을 

알아가는 문제.

돌아가야 길이 보인다.