[Python] 프로그래머스 - 스티커 모으기(2)

문제

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

프로그래머스

풀이

처음에는 재귀 함수를 이용한 완전 탐색으로 접근하려고 했지만 구현해도 시간초과가 뜰것이 분명해서 중간에 포기...

찾아보니 이 문제는 dp를 활용해서 풀 수 있었음.

 

우선 문제의 예시로 점화식을 이해해보면,

[14, 6, 5, 11, 3, 9, 2, 10] 의 배열에서 문제의 조건을 만족하는 최대값을 구한다고 가정해보자(원형이라는 조건 생략)

 

위의 배열에서 하나씩 원소를 늘려나가면서 생각해보면,

부분 배열에 따른 최대값과 각 자리별 최대값을 저장하는dp 배열은 다음과 같아진다.

 

[14] $\rightarrow$ 14 $\rightarrow$ [14]

[14, 6] $\rightarrow$ 14 $\rightarrow$ [14, 14]

[14, 6, 5] $\rightarrow$ 19 $\rightarrow$ [14, 14, 19]

[14, 6, 5, 11] $\rightarrow$ 25 $\rightarrow$ [14, 14, 19, 25]

[14, 6, 5, 11, 3] $\rightarrow$ 14 $\rightarrow$ [14, 14, 19, 25, 25]

...

 

위의 과정에서 규칙을 곰곰히 생각해보면, 새로 원소가 추가될 때 전전의 인덱스의 최대값(dp[idx-2])과 새로 들어온 원소의 합과 바로 전 인덱스의 최대값(dp[idx-1])의 합의 비교로 계산할 수 있다.

 

따라서, dp[i] = max(dp[i-2] + sticker[i], dp[i-1])의 점화식을 세울 수 있다.

 

그런데 문제에서는 주어진 배열이 원의 형태를 띄고 있기 때문에 위의 점화식을 바탕으로 단순히 배열을 순회하면 마지막 원소를 사용할 수 없음에도 사용해서 최대값을 구하기 때문에 잘못된 값이 계산된다.

 

그러므로 첫번째 원소를 사용하는 경우와 사용하지 않는 경우의 두가지 경우로 나눠서 전체의 최대값을 구하면 문제의 정답을 구할 수 있다.

def solution(sticker):
    answer = 0
    # dp(점화식)
    if len(sticker)<=2:
        return max(sticker)
    # 0부터 시작
    dp = [0]*(len(sticker)-1)
    for i,v in enumerate(sticker[:-1]):
        dp[i]=max(dp[i-2]+v, dp[i-1])
    answer = max(answer, dp[-1])
    # 1부터 시작
    dp = [0]*(len(sticker)-1)
    for i,v in enumerate(sticker[1:]):
        dp[i]=max(dp[i-2]+v, dp[i-1])
    answer = max(answer, dp[-1])
    
        
    return answer