[2020 카카오 인턴십] 스티커 모으기(2)

문제 설명

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

프로그래머스

문제 풀이

• 1칸 띄워서 계산하는 문제이므로 개수가 3개 이하라면 그 수들 중 가장 큰 수가 정답이 됨.
  • a, b, c 일 땐 a와 c도 합체가 안되므로 
• dp [n]=max(s [n]+dp [n-2], dp [n], s [n]+dp [n-3] ) 
• 경우의 수
  1. 첫 번째 수부터 계산(이 경우 마지막 숫자는 빼줘야 함)
  2. 두 번째 수부터 계산(이 경우 마지막 숫자도 더하기 가능)
  3. 세 번째 수부터 계산(이 경우 마지막 숫자도 더하기 가능) -> 굳이 따로 계산할 필요 없이 1번의 경우의 수에서 마지막 수까지 다 더한 후 첫 번째 수를 빼면 됨 

소스코드

from collections import deque

dx = [2,3]
def solution(s):
    answer = 0
    n = len(s)
    if(n<=3):
        return max(s)
    dp = [[0]*n for i in range(2)]
    dp[0][0]=s[0]
    dp[1][1]=s[1]
    for j in range(2):
        for i in range(2,n):
            for k in range(2):
                num = i-dx[k]
                if(num<0):
                    continue
                dp[j][i]=max(dp[j][num]+s[i],dp[j][i])
    dp[0][-1]-=s[0]
    answer = max(max(dp[1]),max(dp[0]))
    return answer


print(solution([14, 6, 5, 11, 3, 9, 2, 10]))