[프로그래머스] 코딩테스트 연습 - 스티커 모으기(2) (Python)

코딩테스트 연습 - 스티커 모으기(2) [Summer/Winter Coding(~2018)]

코딩테스트 연습 - 스티커 모으기(2)

문제를 처음 봤을 땐 홀수번째 수의 합과 짝수번째 수의 합 중에서 큰 것만 반환하면 되는 줄 알았네요...

당연하게 문제를 틀리고 문제 설명을 천천히 다시 읽어보며 생각해보니 풀이 방향이 조금 생각났습니다ㅎㅎ

 

풀이

문제에서 필요한 알고리즘 풀이 방법은 DP입니다.

반복문을 통해 스티커들의 수를 차례대로 확인한다고 했을 때, 어떤 수를 추가해야 최댓값이 될지 모르는 상황이기 때문에 현재 인덱스의 수 A를 추가할지, 추가하지 않을지를 결정해야 합니다.

 

그렇면 확인해야 하는 두 가지의 경우는 아래와 같이 계산할 수 있습니다.

\( \quad \bullet \) DP [Index-1] \( \Rightarrow \) 현재 인덱스의 수를 추가하지 않는 경우

\( \quad \bullet \) DP [Index-2] + sticker [Index] \( \Rightarrow \) 현재 인덱스의 수를 추가하는 경우

위 두 가지 경우중 더 큰 수가 되는 것을 기억하고 다음 인덱스에서도 똑같은 과정을 반복하면 됩니다.

한 가지 추가적으로 확인해야 하는 것은 첫 번째 스티커를 뜯게 되면 마지막 스티커를 사용하지 못하게 되는 것입니다.

 

Code

def solution(sticker):
    if len(sticker) == 1: return sticker[0]
    answer = [[0 for i in range(len(sticker))] for j in range(2)]
    answer[0][0:2] = [sticker[0], sticker[0]]
    answer[1][1] = sticker[1]

    for idx in range(2, len(sticker)):
        answer[0][idx] = max(answer[0][idx-1], answer[0][idx-2]+sticker[idx])
        answer[1][idx] = max(answer[1][idx-1], answer[1][idx-2]+sticker[idx])

    return max(answer[0][-2], answer[1][-1])

 

 

문제 설명

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

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

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

제한 사항

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

 

 

입출력 예

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