[프로그래머스] LV.3 스티커 모으기(2) / 파이썬(Python)

 

📜 문제 설명

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

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

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

 

 

제한사항

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

 

🔗 문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/12971#

프로그래머스

 

💡 문제 풀이

DP 문제

주어진 배열에서 최대값이 될 수 있는 조합을 만드는 문제이다. 이 때 제한사항은 내가 선택한 값의 양 옆의 값은 고르지 못한다. 스티커가 둥글게 이어졌다는 가정이기 때문에 배열의 첫 번째 값과 마지막 값도 이어져 있는 것으로 간주한다.

그래서 경우의 수는 크게 보면 결국 두 가지이다. 배열의 첫 번째 값을 가지고 가거나 마지막 값을 가지고 가거나이다.

두 경우 모두 2번 째 전 값에 현재 값을 더한 값, 1번째 전 값 중에 큰 값만 선택해가면 가질 수 있는 최대의 값이 나온다.

 

1트. 슬라이싱을 사용했다가 효율성에서 털렸다.

def solution(sticker):
    answer = 0
    if len(sticker) <= 2:
        return max(sticker)
    
    first, last = sticker[:2], sticker[1:3]
    
    for i in range(2, len(sticker) - 1):
        tmp = first[:len(first) - 1]
        first.append(sticker[i] + max(tmp))
        
    
    for j in range(3, len(sticker)):
        tmp = last[:len(last) - 1] 
        last.append(sticker[j] + max(tmp))
    
    return max(max(first), max(last))

 

2트. 논리는 같지만 배열을 채워나가는 방식으로 풀어서 성공했다.

def solution(sticker):
    answer = 0
    if len(sticker) <= 2:
        return max(sticker)
    
    check = [[0, 0] for _ in range(len(sticker))]
    
    check[0][0] = sticker[0]
    check[1][0] = check[0][0]
    check[1][1] = sticker[1]
    
    for i in range(2, len(sticker)):
        check[i][0] = max(check[i-2][0] + sticker[i], check[i-1][0])
        check[i][1] = max(check[i-2][1] + sticker[i], check[i-1][1])
    
    return max(check[-1][1], check[-2][0])