LV3 스티커 모으기 (2) (Python)

 

---

 

문제

 

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

프로그래머스

 

풀이

 

dp 문제이다. 

 

1. dp 점화식 

 

d라는 dp 배열이 있을때 d[n]은 n번째 티켓까지 고려했을 때 가장 높은 점수가 들어가 있다고 가정하자.

이후 점화식을 어떻게 세울지 고민해보면 된다.

 

만약 내가 n번째 티켓을 고른다고 생각해보자. 그러면 n-1번째 티켓 값은 사용하지 못할것이다. 그리고 d[n-2] 값에 현재 고른 티켓값을 합치면 될 것이다.

 

n번째 티켓을 고르지 않는다면? d[n-1] 값이 현재 누적된 가장 큰 값이니 이 값을 가져오면 된다.

 

따라서 d[n] = max(d[n-2] + ticket[n], d[n-1]) 이 점화식이 된다.

 

 

2. 초기화

 

단, 주의할 점이 있는데 dp 를 활용하려면 초기값이 필요하다

초기값 또한 첫티켓을 사용하냐, 두번째 티켓을 사용하냐 2가지로 나뉜다. 

따라서 2개의 dp배열을 선언해주어야 한다.

 

이어서 dp배열은 어떻게 변화되는지 알아보자.

 

첫번째 티켓을 사용한 경우에는 

d[0] = sticker[0] 일 것이며, 그 다음 티켓 값은 사용하지 못하니

d[1] = d[0] 이 될 것이다.

 

첫번째를 사용하지 않고 두번째를 사용하는 경우에는

d[1] = sticker[1] 로 선언해주면 된다.

 

 

3. 반복

 

우선 우리는 두 초기값에 대해서 d[0], d[1] 에 초기화를 해주었기에 d[2]부터 값을 구해주면 된다.

 

첫번째 티켓을 사용한다고 가정했을때, 주의할 점이 있다. 마지막 티켓값은 사용하지 못한다는 것이다. (원형이니까)

따라서 for문으로 반복을 하되, 마지막 요소는 제외하고 반복해야한다.

 

두번째 티켓을 사용하는 경우에는 정상적으로 끝까지 반복해주면 된다.

 

4. 예외

 

길이가 1이나 2인 경우에는 예외처리 해주자!

 

 

코드

def solution(sticker):
    l = len(sticker)

    if l == 1: return sticker[0]
    if l == 2: return max(sticker)

    d = [0] * l
    d_copy = [0] * l

    # 첫번째 스티커를 사용하는 경우
    d[0] = sticker[0]
    d[1] = d[0]
    for i in range(2, l-1):
        d[i] = max(d[i-2] + sticker[i], d[i-1])

    # 두번째 스티커를 사용하는 경우
    d_copy[1] = sticker[1]
    for i in range(1, l):
        d_copy[i] = max(d_copy[i-2] + sticker[i], d_copy[i-1])

    return max(d[l-2], d_copy[l-1])

 

후기

 

dp는... dp는 정말 어렵다. 찾아서 풀고 싶진 않으나, 만나면 피하지 말자..