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

스티커 모으기(2)

프로그래머스

 

내 풀이

• 첫번째 값을 선택하는 경우/ 선택 안하는 경우로 구분
• 첫번째 값 선택하는 경우 → 마지막 값은 선택 할 수 없음
  • i번째 값 선택할지 말지로 dp진행
    • i 값 선택하는 경우
      • i-1 선택 못하고 i-2는 선택해도 되고 안해도 되고
      • max(dp[i-2])+sticker[i]
    • i 값 선택 안하는 경우
      • i-1값 선택해도 되고 안해도 되고
      • max(dp[i-1])
  • 마지막 값 선택 안 하는 경우로 선택
    • max(answer,dp[n][1])
• 첫번째 값 선택 안하는 경우 → 마지막 값 선택 해도 되고 안해도 됨
  • dp 진행한 뒤에 마지막 값은 둘 중에 최댓값 선택
    • max(answer,max(dp[n]))

def solution(sticker):
    answer = 0
    n=len(sticker)
    sticker=[0]+sticker
    
    if n<=2:
        return max(sticker)
    
    for j in range(2):
        dp=[[-float('inf') for _ in range(2)] for _ in range(n+1)]
        dp[0][0]=0
        dp[0][1]=0
        if j==0:
            dp[1][j]=sticker[1]
        else:
            dp[1][j]=0
            
        for i in range(2,n+1):
            dp[i][0]=max(dp[i-2])+sticker[i]
            dp[i][1]=max(dp[i-1])
        
        if j==0:
            answer=max(answer,dp[n][1])
        else:
            answer=max(answer,max(dp[n]))
    
    return answer

 

 

다른 사람 풀이

•  1번 선택하는 경우
  • 1 ~ n-1번 배열만 확인
  • dp1 = [0] + sticker[:-1]
• 2번 선택하는 경우
  • 2 ~ n번 배열만 확인
  • dp1 = [0] + sticker[1:]

def solution(sticker):
    answer = 0
    if len(sticker) == 1:
        return sticker.pop()

    size = len(sticker)
    # 1번 선택하는 경우 -> 1..n-1번 배열에 대한 DP
    dp1 = [0] + sticker[:-1]
    for i in range(2, size):
        dp1[i] = max(dp1[i-1], dp1[i-2] + dp1[i])
    
    # 2번 선택하는 경우 -> 2...n번 배열에 대한 DP
    dp2 = [0] + sticker[1:]
    for i in range(2, size):
        dp2[i] = max(dp2[i-1], dp2[i-2] + dp2[i])
        
    answer = max(dp1[-1], dp2[-1])
    return answer