사용자 도구

사이트 도구


ps:problems:programmers:42897

도둑질

ps
링크https://programmers.co.kr/learn/courses/30/lessons/42897
출처프로그래머스
문제 번호42897
문제명도둑질
레벨Level 4
분류

동적계획법

시간복잡도O(n)
인풋사이즈n<=1,000,000
사용한 언어Python
해결날짜2020/12/11

풀이

  • 원형이 아니라 직선으로 배열되어 있다면 아주 평범한 1차원 DP가 된다.
    • dp[i]을 i번째 집까지에서 훔칠수 있는 최대 액수라 하면,
      • dp[i] = max(i번째 집에서 안훔치는 경우, i번째 집에서 훔치는 경우) = max(dp[i-1], dp[i-2] + money[i])
    • 으로 쉽게 정리된다
  • 이 문제에서는 원형이라서, 첫번째 집을 털었을 경우에는 마지막 집을 털수 없다는 조건이 추가되어 약간 복잡해진다.
    • 마지막 집을 안털거나, 첫번째 집을 안털거나, 두가지 경우로 나누어서 각각 최대값을 구한 뒤, 다시 그 둘 중에서 최대값을 구하면 된다.
    • 구현하는 방법은, 첫번째 집을 털었을 때와 안털었을 때로 나누어 두개의 dp 테이블을 만들어 계산한다.
      • dp1[i] 은 i번째 집까지에서 훔칠 수 있는 최대 액수이다
      • dp2[i] 은 첫번째 집을 털지 않고서 i번째 집까지에서 훔칠 수 있는 최대 액수이다
    • 이렇게 두면, 최종적으로 구하는 값은 마지막 집을 안턴 dp1[n-1]과, 첫번째 집을 안턴 dp2[n]중 최대값이 된다.
  • dp식이 이전 2항에 대한 점화식이므로, 슬라이딩 윈도우를 써서 공간복잡도 O(1)에 구현할 수 있다.

코드

"""Solution code for "Programmers 42897. 도둑질".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/42897
- Solution link: http://www.teferi.net/ps/problems/programmers/42897
"""

def solution(money):
    dp1, dp1_cur = [0, money[0]], max(money[0], money[1])
    dp2, dp2_cur = [0, 0], money[1]
    for m in money[2:]:
        dp1[-1], dp1[-2] = dp1_cur, dp1[-1]
        dp2[-1], dp2[-2] = dp2_cur, dp2[-1]
        dp1_cur = max(dp1[-1], dp1[-2] + m)
        dp2_cur = max(dp2[-1], dp2[-2] + m)
    return max(dp1[-1], dp2_cur)

토론

댓글을 입력하세요:
S Y Y I D
 
ps/problems/programmers/42897.txt · 마지막으로 수정됨: 2021/01/21 14:56 저자 teferi