[프로그래머스] 도둑질 [동적 계획법]

programmers.co.kr/learn/courses/30/lessons/42897?language=python3#

코딩테스트 연습 - 도둑질

도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다.

각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 두 집을 털면 경보가 울립니다.

각 집에 있는 돈이 담긴 배열 money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최댓값을 return 하도록 solution 함수를 작성하세요.

제한사항

• 이 마을에 있는 집은 3개 이상 1,000,000개 이하입니다.
• money 배열의 각 원소는 0 이상 1,000 이하인 정수입니다.

입출력 예

money	return
[1, 2, 3, 1]	4

풀이

마을은 동그랗게 배치되어 끝과 끝이 서로 인접하므로, 첫 번째 집을 털었을 경우와 털지 않았을 경우를 나누어 진행하여야 합니다. 또한, 파이썬3의 경우 O(n)으로 풀어도 구현 방법에 따라 효율성 테스트에서 시간 초과가 발생하는 경우가 있어 유의해야 합니다.

인접하지 않는 집의 가치를 더한 값과 이전까지 max 값을 비교하여 가장 큰 값이 남도록 만듭니다. 문제에서 준 테스트케이스를 이용하여 표현해볼까요?

house value	include the first house		exclude the first house
	previous maximum	current value	previous maximum	current value
1	0	1	0	0
2	1	2	0	2
3	2	1+3=4	2	3
1	4	2+1=3	3	2+1=3
max	4

 

 

 

이번에는 새로운 테스트케이스를 대상으로 값을 구해봅시다. money = [1, 3, 4, 3, 7], answer = 11입니다.

house value	include the first house		exclude the first house
	previous maximum	current value	previous maximum	current value
1	0	1	0	0
3	1	3	0	3
4	3	1+4=5	3	4
3	5	3+3=6	4	3+3=6
7	6	5+7=12 (첫 집이 포함됨, max 시 제외되어야 함)	6	4+7=11
max	11

money = [4, 6, 4, 3, 7], answer = 15

house value	include the first house		exclude the first house
	previous maximum	current value	previous maximum	current value
4	0	4	0	0
6	4	6	0	6
4	6	4+4=8	6	4
3	8	6+3=9	6	6+3=9
7	9	8+7=15 (첫 집이 포함됨, max 시 제외되어야 함)	9	6+7=13
max	15

 

다음 문제는 코드를 어떻게 효율적으로 작성할까...인데 이 부분은 직접 경험해보며 확인해봐야 할 것으로 보입니다. 같은 구문을 수행하는 코드일지라도 수행 시간이 미묘하게 달라 시간 초과가 발생하기 때문입니다.

max(dp[i-1][:2]) # 통과
max(dp[i-1][0], dp[i-1][1]) # 시간 초과

첫 번째 집을 포함하는가, 하지 않는가로 케이스를 나눠 for loop으로 수행해도 시간 초과가 발생합니다. 시간 초과 코드는 케이스를 나눈 것 때문에 if 문 같은 군더더기가 붙기 때문입니다. 통과 코드는 한 loop 안에 계산하기 때문에 미묘한 차이가 발생합니다..!

# 시간 초과
def solution(money):
    answer = 0
    for first in [True, False]:
        dp = [[0, 0] for i in range(len(money)-1)]
        if first:
            dp[0][1] = money[0]
            
        for i in range(1, len(dp)):
            dp[i][0] = max(dp[i-1][:2])
            dp[i][1] = dp[i-1][0] + money[i]
        
        if not first:
            dp[-1][0] += money[-1]
            
        dp[-1].append(answer)
        answer = max(dp[-1])
    return answer
    
# 통과
def solution(money):
    dp = [[0, 0, 0, 0] for i in range(len(money)-1)]
    dp[0][1] = money[0]
            
    for i in range(1, len(dp)):
        dp[i][0] = max(dp[i-1][:2])
        dp[i][1] = dp[i-1][0] + money[i]
        dp[i][2] = max(dp[i-1][2:])
        dp[i][3] = dp[i-1][2] + money[i]
        
    dp[-1][2] += money[-1]
    return max(dp[-1])

번외. 배열을 사용하지 않고 계산하는 방법도 있습니다. 비슷한 규칙을 적용하지만, 변수 세 개의 값을 밀어내며 사용하는 부분이 인상적입니다. 마지막에 최댓값을 구할 때, 첫 번째 집을 포함한 경우에는 마지막 집과 첫 번째 집이 인접하기 때문에 z1을 포함하면 안 되며, 마지막 집을 포함하는 경우에는 마지막 집을 계산하는 공식에 따라 x2, y2가 z2보다 항상 작거나 같기 때문에 포함하지 않아도 됩니다.

def solution(money):
	# include the first house
    x1, y1, z1 = money[0], money[1], money[0]+money[2]
    
    # exclude the first house
    x2, y2, z2 = 0, money[1], money[2]
    
    for i in money[3:]:
    	# 하나씩 밀어가며 새로운 집 포함 시 금액 계산
        x1, y1, z1 = y1, z1, max(x1, y1)+i
        x2, y2, z2 = y2, z2, max(x2, y2)+i
    
    # z1 = 첫 집 포함의 마지막 집 (원형으로 인접함)
    # z2가 max(x2, y2) + i이므로, x2, y2 < z2
    return max(x1, y1, z2)

max(dp[:2]) 시에는 조건에 맞는 배열을 새로 생성하는 오버헤드가 있으나, 위 경우에는 max 시에도 변수를 사용하기 때문에 효율성 테스트 시 훨씬 빠릅니다.