[프로그래머스 lv 4] 도둑질

사용 언어 - Python3

문제 - 도둑질

프로그래머스

 

 

 

정답

DP 규칙 찾기 (정답 맞춘 여부 X) 

인접한 집은 못 털기 때문에, 아래의 점화식이 성립한다.

dq[i] = max(dq[i-1], money[i] + dq[i-2])

인접한 집 털거나, 현재 집과 전전집 털기 중 max값으로 업데이트

 

원의 형태라 1번집과 마지막집은 인접해, 같이 털지 못한다.

1번집을 터는 경우와 안터는 경우로 구분해서 계산한다.

• 1번집을 털면, 마지막 집은 털지 못하기 때문에 범위가 len(money)-1까지만 계산한다.
• 1번집을 안털면, 첫번째 원소를 0으로 지정하고, 범위는 끝까지 지정한다.

1번집을 터는 경우의 max는 가장 마지막 집을 제외한 마지막 값인 dq1[-2]이다.

1번집을 안터는 경우의 max는 가장 마지막 값인 dq2[-1]이다.

두 값의 최대값을 구하면 정답이다.

def solution(money):
    # 1번 집을 터는 경우
    dp1 = [0] * len(money)
    dp1[0] = money[0]
    for i in range(1, len(money) - 1):  # 마지막 집은 털지 못함
        dp1[i] = max(dp1[i - 1], money[i] + dp1[i - 2])

    # 1번 집을 안터는 경우
    dp2 = [0] * len(money)
    dp2[0] = 0
    for i in range(1, len(money)):
        dp2[i] = max(dp2[i - 1], money[i] + dp2[i - 2])

    return max(dp1[-2], dp2[-1])

 

 

 

 

레퍼런스

• 정답 깃허브

GitHub - yyeongeun/codingtest: 코딩테스트 공부