House Robber II

문제

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

입력

1 <= nums.length <= 100 // 집 개수
0 <= nums[i] <= 1000 // 재산

결과

ans: Int = 훔칠 수 있는 최대 금액

해석

이전 문제와 동일하지만 제약조건이 하나 추가되었다

바로 집 배치가 원형인 점, 이렇게 되면 첫번째 집과 마지막 집도 이웃이되기 때문에 이전 코드는 불가능

 

첫 번째 집을 방문하면 마지막 집은 무조건 포기한다.

첫 번째 집을 방문하지 않고 n-2 번째도 방문하지 않았다면 n번째 집을 방문할 수 있다.

 

그렇기 때문에 출발 지점과 끝지점이 2개의 경우의 수로 나뉘기 때문에

2번의 순회는 필수 불가결

 

코드

class Solution {
    func rob(_ nums: [Int]) -> Int {
        let n = nums.count
        if n <= 2 {
            return nums.max()!
        }

        return max(solve(nums,0, n-1), solve(nums,1,n))
    }

    func solve(_ nums: [Int], _ start: Int, _ end: Int) -> Int {
        var prevTwoStep: Int = 0
        var prevOneStep: Int = 0

        for i in start..<end {
            let newResult = max(prevOneStep, prevTwoStep + nums[i])
            prevTwoStep = prevOneStep
            prevOneStep = newResult  
        }
        return prevOneStep
    }
}