[파이썬] 프로그래머스 : 도둑질 (Lv.4)

[파이썬] 프로그래머스 : 도둑질 (Lv.4)

프로그래머스

---

풀이

방향성 생각

• 첫 집을 터는 경우, 털지 않는 경우 두가지 상태로 나누어서 풀이

전체코드

def solution(money):
    
    n = len(money)
    if n<3:
        return max(money[:2])

    dp = [[0]*n for _ in range(2)] # dp[첫 집 터는 유무][위치]

    dp[0][:2] = [0,money[1]]
    dp[1][:2] = [money[0],max(money[:2])]
    
    for state in range(2):
        for stage in range(n-2):
            dp[state][stage+2] = max(dp[state][stage+1], dp[state][stage] + money[stage+2])

    return max(dp[0][-1],dp[1][-2])

• n<3인 경우 둘중에 값이 큰 집 선택
• DP 초기화
  첫 집을 선택하지 않으면 dp[0][0] = 0, 이후 집을 선택하면 dp[0][1] = money[1]
  첫 집을 선택하면 dp[1][0] = money[0], dp[1][1] = 쉬고 선택 or 선택하고 쉬기 중에 큰거
• dp[1][-1]은 경보 울리는 케이스라 답에서 제외

코멘트

스티커 모으기랑 똑같음