프로그래머스 스티커 모으기 (python, 파이썬)

• 문제 설명

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

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

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

---

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

---

• 입/출력

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

---

• 코드

def solution(sticker):
    n = len(sticker)
    
    # 맨 처음 스티커를 떼었을 때
    dp = [0] * n
    dp[0] = sticker[0]
    if n == 1:
        return max(dp)
    
    dp[1] = sticker[1]
    if n == 2:
        return max(dp)
    
    dp[2] = max(sticker[1], sticker[0]+sticker[2])
    if n == 3:
        return max(dp)
    
    for i in range(3, n-1):
        dp[i] = max(dp[i-3]+sticker[i], dp[i-2]+sticker[i], dp[i-1])
    
    # 맨 처음 스티커를 떼지 않을 때
    dp2 = [0] * n
    dp2[0] = 0
    dp2[1] = sticker[1]
    dp2[2] = max(sticker[1], sticker[2])
    
    for i in range(3, n):
        dp2[i] = max(dp2[i-3]+sticker[i], dp2[i-2]+sticker[i], dp2[i-1])
        
    return max(max(dp), max(dp2))

dp를 적용했다.

 

맨 처음 스티커를 뗄 경우

sticker[0]

sticker[1]

max(sticker[1], sticker[0] + sticker[2])

max(dp[i-3]+sticker[i], dp[i-2]+sticker[i], dp[i-1])

처음과 두번째는 해당 스티커를 사용하는 경우 밖에 없고 세번째는 두번째 스티커를 이용하는 경우와 첫번째 세번째를 떼는 경우를 비교해주면 됩니다.

 

네번째부터는 해당 스티커와 i-3번째 스티커, 해당스티커와 i-2번째스티커, i-1번째는 해당스티커를 이용못하기때문에(이웃해있어서) 3개의 값을 비교해주면된다.

 

 

맨 처음 스티커를 떼지않을 경우

0

sticker[1]

max(sticker[1] + sticker[2])

max(dp[i-3]+sticker[i], dp[i-2]+sticker[i], dp[i-1])

처음에 0을 넣어주고 3번째에는 2번쨰스티커와 3번째스티커중 비교하고 4번째 부터는 위와 동일하다.

---

• 출처

https://programmers.co.kr/learn/courses/30/lessons/12971?language=python3