[LeetCode C++] 213. House Robber II

2021. 10. 11. 13:34· Coding test/Leet Code
목차
  1. ⭐️ 난이도
  2. ⭐️ 문제
  3. ⭐️ Follow-up
  4. ⭐️ Idea flow
  5. ⭐️ Code
  6. ⭐️ Feedback
728x90

⭐️ 난이도

Medium

 


⭐️ 문제

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

당신은 거리에 있는 집들을 따라서 도둑질 할 계획을 세우고 있는 프로 도둑이다.

각 집마다 일정한 양의 돈이 있다.

모든 집은 원의 형태를 띄고 있다. 즉, 첫 번째 집의 이웃은 마지막 집이다.

인접한 집에는 모두 경비 시스템이 연결되어 있는데, 만일 인접한 두 집이 같은 날에 침입당한다면, 자동으로 경찰이 출동할 것이다.

 

각 집에 쌓여있는 돈에 대한 정보 배열 nums가 주어졌을 때, 경찰이 출동하지 않게 하면서 돈을 최대 얼마 도둑질할 수 있는지 구하시오.

 


⭐️ Follow-up

X

 


⭐️ Idea flow

 

이 문제에서 주어진 조건을 보면, 집이 원의 형태를 띄고 있다고 주어져있다.

첫 번째 집과 마지막 집이 바로 인접한 집임을 알 수 있는데, 이것이 문제를 푸는데에 가장 결정적인 포인트였다.

 

첫 번째 예시를 보면 주어진 집이 총 3개이다.

첫 번째 집을 도둑질 했으므로, 세 번째(마지막) 집을 도둑질 하지 못할 것이다.

 

그렇다면 집이 총 3개 일 때에만 이러한 제한이 걸리는걸까?

아니다. 집의 개수에 상관 없이 

1) 만일 첫 번째 집을 도둑질 했다면, 마지막 집을 도둑질 하지 못한다.

2) 만일 첫 번째 집을 도둑질하지 않았다면, 마지막 집을 도둑질 할 수 있다.

 

따라서 검사하는 범위를 두 개로 나누어서 DP를 진행하고, 두 개의 케이스 중에서 더 큰 값을 반환하면 된다.

 

 

 


⭐️ Code

class Solution {
public:
    int solve(vector<int>& nums, int s, int e){
        vector<int> dp(nums.size());
        dp[s] = nums[s];
        dp[s + 1] = max(nums[s], nums[s + 1]);
        
        for(int i = s + 2; i < e; i++){
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        return dp[e - 1];
    }
    
    int rob(vector<int>& nums) {
        if(nums.size() == 1)    return nums[0];
        if(nums.size() == 2)    return max(nums[0], nums[1]);
        
        return max(solve(nums, 0, nums.size() - 1), solve(nums, 1, nums.size()));
    }
};

 

 


⭐️ Feedback

 

검사하는 범위를 두 개로 나누어서 진행을 하면 된다는 것 까지는 생각을 하고, 시작점과 끝점을 매개변수로 전달을 했다.

하지만 내가 한 방법보다 더 효율적인 방법이 있을 것 같아 다른 사람들의 코드를 둘러보았다.

 

vector를 반복자를 이용하여 생성하는 방법과, int형 배열의 크기를 바로 지정하면 된다는 것을 복기할 수 있었다.

class Solution {
public:
    int solve(vector<int>& nums){
    	// int형 배열이 필요한 크기를 알고 있다면..
        int dp[nums.size()];
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);
        
        for(int i = 2; i < nums.size(); i++){
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        return dp[nums.size() - 1];
    }
    
    int rob(vector<int>& nums) {
        int len = nums.size();
        if(len == 1)    return nums[0];
        if(len == 2)    return max(nums[0], nums[1]);
        
        // 반복자를 통해 새로운 vector에 들어갈 내용물을 정할 수 있다.
        vector<int> dp1(nums.begin(), nums.end() - 1);
        vector<int> dp2(nums.begin() + 1, nums.end());
        
        return max(solve(dp1), solve(dp2));
    }
};

 

728x90
  1. ⭐️ 난이도
  2. ⭐️ 문제
  3. ⭐️ Follow-up
  4. ⭐️ Idea flow
  5. ⭐️ Code
  6. ⭐️ Feedback
'Coding test/Leet Code' 카테고리의 다른 글
  • [LeetCode C++] 283. Move Zeroes
  • [LeetCode C++] 740. Delete and Earn
  • [LeetCode C++] 70. Climbing Stairs
  • [LeetCode C++] 98. Validate Binary Search Tree
HEY__
HEY__
안녕하세요 :) 공부하며 배운 것들을 기록하기 위한 블로그입니다. 도움이 되시길 바라며 혹시 잘못된 점이 있다면 댓글 부탁드립니다! :D
250x250
HEY__
while(true) { continue; }
HEY__
전체
오늘
어제
  • 분류 전체보기 (164)
    • Spring Boot (45)
      • 스프링 입문 강의 (18)
    • AWS (8)
    • 프로젝트 (6)
    • Network (21)
    • Operating System (8)
    • Database (4)
    • ETC (2)
    • Java (3)
    • C++ (7)
    • Python (1)
    • 도서 📚 (3)
      • Effective Java (3)
    • Coding test (50)
      • Baekjoon (30)
      • Leet Code (18)
      • Programmers (2)
    • Algorithm (C++) (5)

블로그 메뉴

  • 태그
  • Github
  • 글쓰기
  • 블로그관리

공지사항

인기 글

태그

  • Spring
  • spring boot
  • Network
  • Java
  • leetcode
  • slack
  • Algorithm
  • kotlin
  • HTTP
  • C++
  • CPP
  • OS
  • Servlet Container
  • coding test
  • Baekjoon
  • dispatcher servlet
  • programmers
  • STL
  • aws
  • Cloudfront

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.0
HEY__
[LeetCode C++] 213. House Robber II
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.