프로그래머스(programmers) 도둑질 python 정답[동적계획법 풀이]

프로그래머스(programmers) 도둑질 python 정답[동적계획법 풀이]

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/42897

프로그래머스

문제 정답

def solution(money):
	# 둘 다 안터는 경우는 존재하지 않는다.
    return max(visitLastSkipFirst(money), visitFirstSkipLast(money))


def visitFirstSkipLast(money): # 마지막 집을 안터는 경우
    dp1 = [0] * len(money)
    dp1[0] = money[0] # 첫번째 집 방문
    dp1[1] = max(money[0], money[1]) # 첫번째 집을 터는경우, 안터는 경우의 최대값

    for i in range(2, len(money)-1): # skip last
        dp1[i] = max(dp1[i-1], money[i]+dp1[i-2])
    return max(dp1)

def visitLastSkipFirst(money): # 첫번째 집을 안터는 경우
    dp2 = [0] * len(money)
    dp2[0] = 0 # 첫번째 집 방문 안함
    dp2[1] = money[1] # skip first

    for i in range(2, len(money)): # 마지막 집 방문 
        dp2[i] = max(dp2[i-1], money[i]+dp2[i-2])
    return max(dp2)

문제 해설

이차원을 1차원으로 바꾸어 생각해보자.

이 원을 뚝 짤라서 직선으로 생각해보면, 인접 관계가 표현되지 않는 부분은 마지막 집과 첫번째 집이다.

그리고 서로 인접한 집은 털 수 없기 때문에, 첫번째 집과 마지막 집을 동시에 털 수는 없다.

 

물론 둘 다 안털 수 있다.

예를 들어 1 2 3 4 5 에서 2와 4만 터는게 최대라면 말이다. (1과 5가 마지막 집이고)

 

하지만 둘 다 터는 경우만 존재하지 않는다.

따라서 마지막 집을 절대 안터는 경우, 첫번째 집을 절대 안터는 경우를 계산해서 최대값을 구해준다.

이전 집을 방문한 경우 지금 집을 방문할 수 없으므로, 두칸 전 집을 방문 + 지금 집 방문 혹은 이전 집 방문한 케이스를 dp 해주면 된다.

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