[프로그래머스] Level4 DP문제(by Python)

# 프로그래머스 - 스티커모으기(2)

코딩테스트 연습 - 스티커 모으기(2) | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

def solution(sticker):

    if len(sticker) == 1:
        return sticker[0]
    
    dp = [0 for _ in range(len(sticker))]  # 첫번째 스티커 사용한 경우
    dp2 = [0 for _ in range(len(sticker))]  # 첫번째 스티커 사용하지 않은 경우
     
    dp[0] = sticker[0]
    dp[1] = sticker[0]
     

    dp2[0] = 0
    dp2[1] = sticker[1]
     

    for i in range(2, len(sticker)-1): # 첫번째 스티커 사용했으니까, 마지막 스티커는 사용 못함
        dp[i] = max(dp[i-2] + sticker[i], dp[i-1])
        
    value1 = max(dp)

    for i in range(2, len(sticker)): # 첫번째 스티커 사용하지 않았으니까, 마지막 스티커 사용 가능
        dp2[i] = max(dp2[i-2] + sticker[i], dp2[i-1])
        
    value2 = max(dp2)

    answer = max(value1, value2)
 
    return answer

 

# 도둑질

사실상 같은 문제, 같은 코드로 통과함

 

코딩테스트 연습 - 도둑질 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

def solution(money):
    answer = 0
    n = len(money)
    
    if n == 1:
        return money[0]
    
    dp = [0 for _ in range(n)]
    dp2 = [0 for _ in range(n)]
     
    # 초기화
    dp[0] = money[0]
    dp[1] = money[0]
    
    dp2[0] = 0
    dp2[1] = money[1]
    
    # 첫번째 집 방문 한 경우, 마지막집 방문 못함 
    for i in range(2, n-1):
        dp[i] = max(dp[i-2] + money[i], dp[i-1])
    
    value1 = max(dp)
    
    for i in range(2, n):
        dp2[i] = max(dp2[i-2] + money[i], dp2[i-1])
    
    value2 = max(dp2)
    answer = max(value1, value2)
    # 첫번째 집 방문하지 않은 경우, 마지막집 방문 가능
    return answer