[LeetCode] 213. House Robber 2 (C++)
문제
https://leetcode.com/problems/house-robber-ii/
House Robber II - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
풀이
난이도: Medium
이전 문제를 풀고 오면 굉장히 쉽게 해결할 수 있다.
[LeetCode] 198. House Robber (C++)
[LeetCode] 198. House Robber (C++)
문제 https://leetcode.com/problems/house-robber/ House Robber - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your..
everenew.tistory.com
변한 것은 배열이 원형 배열로 바뀌었다는 것인데,
이로 생기는 차이는 1차원 배열의 가장 첫 원소와 가장 끝 원소가 인접하게 된다는 것이다.
이외의 원소는 원래부터 인접하고 있었기 때문에 이점만 신경을 쓰면 된다.
양 끝 원소가 선택되는 것을 막기 위한 가장 쉬운 방법은 간단히 최댓값을 두 번 찾아주는 것이다.
1. 끝 원소만 포함하지 않는 배열에서의 최댓값
2. 첫 원소만 포함하지 않는 배열에서의 최댓값
이 두 값 중에 더 큰 값이 정답이 된다.
코드
| class Solution { | |
| public: | |
| static int FindMax(vector<int> &nums, int start, int end) { | |
| int prev1=0, prev2=0, now=0; | |
| for (int idx = start; idx<=end; idx++) { | |
| now = max(prev1, prev2 + nums[idx]); | |
| prev2 = prev1; | |
| prev1 = now; | |
| } | |
| return now; | |
| } | |
| int rob(vector<int>& nums) { | |
| if (nums.size() == 1) | |
| return nums[0]; | |
| return max(FindMax(nums, 0, nums.size()-2), FindMax(nums, 1, nums.size() - 1)); | |
| } | |
| }; |