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

문제 링크

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

코딩테스트 연습 - 스티커 모으기(2)

풀이 - 다른 블로그 참고 

• 처음에는 그리디 문제로 접근했는데, 다이나믹 프로그래밍 문제였다.
• result[i]를 sticker에서 i번째 인덱스까지 더했을 때의 최댓값 
• 점화식 : result[i] = max(result[i-1], result[i-2] + sticker[i])
  
  • i-1번 인덱스의 스티커를 뗐을 경우, i번째 스티커는 뗄 수 없으므로 result[i] = result[i-1]
  • i-1번 인덱스의 스티커를 떼지 않았을 경우, result[i] = result[i-2] + sticker[i]
• 첫번째 스티커를 떼는 여부에 따라 두가지로 나눔 
  
  • 떼는 경우, result[0] = sticker[0], result[1] = sticker[0]이며 마지막 인덱스는 확인하면 안된다. 
  • 떼지 않는 경우, result[0] = 0 , result[1] = sticker[1]이며 마지막 인덱스까지 확인한다. 

def solution(sticker):
  answer = 0

  if len(sticker) == 1 :
      return sticker[0]

 # result[i]는 index i번째까지 sticker에서 얻을 수 있는 최댓값 
 
 # 첫번째 스티커 때는 경우 
 # 마지막 인덱스 검사하면 안됨 
  result = [ 0 for _ in range(len(sticker))]

  result[0] = sticker[0]
  result[1] = sticker[0]

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

  answer = max(result)

 # 첫번째 스티커를 안 때는 경우 
 # 마지막 인덱스까지 검사 
  result = [ 0 for _ in range(len(sticker))]

  result[0] = 0
  result[1] = sticker[1] 
  
  for i in range(2, len(sticker)):
    result[i] = max(result[i-1], result[i-2] + sticker[i])
    
  return max(answer,max(result))