[프로그래머스] 스티커 모으기(2) - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

프로그래머스

 

1. 문제 설명

2. 풀이과정

해당 문제는 스티커에 적힌 숫자의 합이 크도록 스티커를 모으는 문제이다.

한 스티커를 떼면 양옆의 스티커를 뗄 수 없으므로 스티커를 뗄 수 있는 방법은 때고 안 떼는 방법(OX)과 안 때고 떼는 방법(XO)이 있다. 두 경우를 각각 DP 알고리즘을 활용하여 해결한다.

DP 알고리즘을 사용하는 이유는 스티커를 하나씩 땔 때 이전에 때었던 스티커의 위치와 값에 영향을 받기 때문이다.

스티커를 떼면 양쪽 스티커를 뗄 수 없기에 현재 스티커를 뗄 지에 대한 위치 영향을 받는 것이고땐 스티커의 값이 최대가 되도록 때야 하기 때문에 현재 스티커를 뗄 지에 대한 값 영향을 받는다.이전의 결과들을 저장하면서 이전 값을 기준으로 위치와 값을 고려해 최적의 경우를 찾아낸다.

 

떼는 첫 번째 스티커의 기준을 전체 스티커의 첫 번째 스티커로 하는지, 두 번째 스티커로 하는지 두 가지 경우로 나누어 해결하였다. 첫 번째 스티커를 떼면 마지막 스티커를 뗄 수 없으므로 마지막 전까지만 고려한다.

첫 번째 스티커를 떼는 경우는 우선 첫 번째 스티커를 무조건 떼는 경우와 첫 번째와 두 번째 스티커 중 더 큰 값을 떼는 경우를 각각 저장하고 다음 스티커부터 전전의 경우(바로 전 스티커 안땜)에 해당 스티커를 떼는 경우와 전의 경우를 비교하여 더 큰 값이 나오도록 스티커를 뗀다.

두 번째 스티커를 떼는 경우는 첫 번째 스티커를 안 떼는 경우와 두 번째 스티커를 떼는 경우를 각각 저장하고 다음 스티커부터는 마찬가지로 전전의 경우에 해당 스티커를 떼는 경우와 전의 경우를 비교하여 더 큰 값이 나오도록 스티커를 뗀다.

 

1. 주어지는 스티커의 개수가 1개이면 if (len(sticker) == 1)
2. 그냥 해당 스티커를 때면 된다. answer = sticker[0]  return answer
3. 첫 번째 스티커를 떼는 경우를 계산할 리스트를 생성한다. li1 = list(0 for _ in range(len(sticker)))
4. 첫 번째 첫 번째 원소에 땐 첫 번째 스티커의 값을 넣는다. li1[0] = sticker[0]
5. 두 번째 원소에 첫 번째 스티커의 값과 두 번째 스티커의 값 중 더 큰 값을 넣는다. li1[1] = max(sticker[0], sticker[1])
6. 세 번째 원소부터 마지막 이전 스티커까지 반복하며 for i in range(2, len(sticker) - 1)
7. 해당 원소에는 전전 원소까지의 누적 값에 해당 스티커를 뗀 경우와 전 원소까지의 누적 값 중 더 큰 값을 저장한다. li1[i] = max(li1[i - 2] + sticker[i], li1[i - 1])
8. 두 번째 스티커를 떼는 경우를 계산할 리스트를 생성한다. li2 = list(0 for _ in range(len(sticker)))
9. 첫 번째 스티커를 떼지 않으므로 두 번째 원소에 두 번째 스티커의 값을 넣는다. li2[1] = sticker[1]
10. 세 번째 원소부터 마지막 스티커까지 반복하며 for i in range(2, len(sticker))
11. 해당 원소에는 전전 원소까지의 누적 값에 해당 스티커를 뗀 경우와 전 원소까지의 누적 값 중 더 큰 값을 저장한다. li2[i] = max(li2[i - 2] + sticker[i], li2[i - 1])
12. 두 경우를 모두 계산하고 두 경우에서 각각 제일 큰 값 두 개를 비교하여 더 큰 값이 최적의 경우이다. 따라서 제일 큰 값을 저장한다. answer = max(max(li1), max(li2))

반응형

3. 소스코드

def solution(sticker):
    answer = 0
    
    if (len(sticker) == 1):
        answer = sticker[0]
        return answer
        
    li1 = list(0 for _ in range(len(sticker)))
    
    li1[0] = sticker[0]
    li1[1] = max(sticker[0], sticker[1])

    for i in range(2, len(sticker) - 1):
        li1[i] = max(li1[i - 2] + sticker[i], li1[i - 1])

    li2 = list(0 for _ in range(len(sticker)))

    li2[1] = sticker[1]
    for i in range(2, len(sticker)):
        li2[i] = max(li2[i - 2] + sticker[i], li2[i - 1])

    answer = max(max(li1), max(li2))

    return answer