Programmers / 스티커 모으기(2) / Python 파이썬

 

*문제 출처는 프로그래머스에 있습니다.

문제 제목: 스티커 모으기(2) (3단계) - 동적 계획법

문제 사이트: https://school.programmers.co.kr/learn/courses/30/lessons/12971#qna

프로그래머스

문제 설명

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

---

    dp1 = [0]
    dp2 = [0]
    dp1.extend([sticker[i] for i in range(len(sticker)-1)])
    dp2.extend([sticker[i] for i in range(1,len(sticker))])

두개의 리스트로 나누어 줍니다~

양쪽 끝이 연결 되어있고 하나의 스티커를 떼면 그 옆의 양쪽 스티커를 못쓰니까 해당 사항을 고려해주어 두개의 리스트로 나눴습니다.

 

그리고 본격적으로 메모이제이션을 하면서 가장 큰 값을 찾아나갈 것입니다.

자 이렇게 보았을 때 16을 사용한다면 16이전 값인 14를 사용하지 못하게 됩니다.

그렇다면 16을 선택하고 14앞의 값인 0은 선택할 수 있을 것입니다.

이제 16+0 이 14보다 큰지를 판단하면서 해당 값을 메모이제이션 하는 것입니다!

 

16+0이 14보다 크므로 우리는 16을 선택하면서 14를 선택하지 못하게 되었습니다.

 

그럼 16은 이제 16과 0을 선택한 상태가 됩니다.

그 다음 인덱스로 가서 생각해봅시다. 이제는 앞에서 했던거처럼 생각하는겁니다.

15를 선택할지 말지는 15의 전 전 값과 더해보고 결정해봅니다.

16(16+0) 보다 15+14가 크면 뭐를 선택하는 것이 이득일까요?

이전에는 16이 컸지만 지금은 14+15를 선택하는 것이 더 이득입니다.

그러면 이제 여기서부터는 15+14가 더 이득인 것을 표시하는 거죠 

이제 15자리는 29(15+14) 가 됩니다.

이제 다음 인덱스로 와서 11 의 전전 인덱스의 값인 16과 전 인덱스 값 29(14+15)를 봅시다

11 + 16 < 29 이므로 29가 더 큰걸 알 수 있네요

그럼 16 + 11 (0+16+11) 을 굳이 선택 안해도 29가 큰걸 알 수 있습니다.

그럼 14+15를 선택하는 것을 유지한다는 뜻으로 11의 인덱스 값은 곧 29 = (14+15) 가 됩니다.

또 이렇게 넘어가면서 이전 선택이 옳은지 비교해나가는 것입니다.

    i = 2
    while i < len(sticker):
        dp1[i] = max(dp1[i-1],dp1[i-2] + dp1[i])
        dp2[i] = max(dp2[i-1],dp2[i-2] + dp2[i])
        i+= 1

나의 풀이

def solution(sticker):
    answer = 0
    if len(sticker) <= 3:
        return max(sticker)
    dp1 = [0]
    dp2 = [0]
    dp1.extend([sticker[i] for i in range(len(sticker)-1)])
    dp2.extend([sticker[i] for i in range(1,len(sticker))])
    
    i = 2
    while i < len(sticker):
        dp1[i] = max(dp1[i-1],dp1[i-2] + dp1[i])
        dp2[i] = max(dp2[i-1],dp2[i-2] + dp2[i])
        i+= 1


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

 

---

※ 알아야 할 것

- 맨앞을 0으로 채워 두개의 리스트로 나눈다

- 값을 비교해나간다