[LeetCode] 198. House Robber (C++)

문제

 

https://leetcode.com/problems/house-robber/

House Robber - LeetCode

 

풀이

 

난이도: Medium 

 

배열로 나타난 주택들에서 인접하지 않는 원소들의 최대합을 구하는 문제.

현재 배열의 위치를 now라고 할 때 1칸 전의 위치를 prev1, 2칸 전을 prev2라고 하자.

prev1에는 prev1까지의 인접하지 않는 최대합을, prev2에는 prev2까지의 최대합을 저장한다.

 

이제 이 두값을 이용해 now까지의 인접하지 않는 최대합을 구해보자.

now를 선택하기 위해서는 인접한 prev1 위치는 선택되선 안 된다.

따라서 now를 선택한다면 prev2까지의 합에 now의 값을 더하면 된다. (= prev2 + now의 값)

 

만약 now를 선택하지 않는다면 prev1의 위치가 선택되었을 수 있는 prev1 값을 사용하면 된다.

 

now까지의 최대합은 now를 선택한 경우와 선택하지 않는 경우, 두 값을 비교하여 더 큰 값이 된다.

now = max(prev1, prev2 + now_value);

 

예를 들어 [2,4,1,2,7]에서는 4와 7이 선택된 경우가 최대 합이 된다.

 

코드