Go, Vantage point
가까운 곳을 걷지 않고 서는 먼 곳을 갈 수 없다.
Github | https://github.com/overnew/
Blog | https://everenew.tistory.com/
티스토리 뷰
문제
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. 첫 원소만 포함하지 않는 배열에서의 최댓값
이 두 값 중에 더 큰 값이 정답이 된다.
코드
'알고리즘 공부 > LeetCode' 카테고리의 다른 글
| [LeetCode] 55. Jump Game (C++) (0) | 2021.11.03 |
|---|---|
| [LeetCode] 91. Decode Ways (C++) (0) | 2021.11.02 |
| [LeetCode] 198. House Robber (C++) (0) | 2021.10.29 |
| [LeetCode] 377. Combination Sum 4 (C++) (0) | 2021.10.28 |
| [LeetCode] 139. Word Break (C++) (0) | 2021.10.25 |