[Leet code - 198] House Robber ✅

문제

Input : 정수배열 nums

Output : 규칙에 맞는 각 원소들의 최대 합

※ 규칙 : n을 선택했을 시, 양 옆의 n - 1과 n +1은 선택 불가능하다.

 

시간 복잡도

※1초에 1억 번을 대략적인 기준으로 삼는다.

 

$1\le n \le 100$

• $2^n\ =\ 2^{100}$❌
  

  

  아승기는 아니였다

• $n^2\ =\ 10,000$✅
  $n^2$이하의 접근을 목표로 하자.

 

 

해결 계획

조금 더 빠른 방법을 생각하다가, 뭔가 저장을 하면서 하면 빠를 것 같은데?라는 생각이 들었다.

어차피 선택 or 선택 안 함의 연속이기 때문에 각 경우의 최대 값을 저장해 가면서 진행하면 되겠다고 생각했다.

table[n][0] = n번째를 선택하지 않았을 때 0 ~ n까지의 최대 합
table[n][1] = n번째를 선택했을 때 0 ~ n까지의 최대 합

 

이런 식으로 처음에는 단순히 OXOX 혹은 XOXO의 경우만 생각하여, 다음과 같은 식을 생각했다.

table[n][0] = table[n - 1][1];
table[n][1] = table[n - 1][0] + nums[n];

 

이렇게 풀이할 경우, 문제 내의 예제처럼 간단한 문제는 정답이 도출되었다.

 

그 후 예외를 생각해 보다가, 혹시 OXXOX처럼 두 번 건너뛰어야 정답인 경우는 없을까? 생각이 들어 예외 케이스를 발견했다.

nums = [2,1,1,100,1], 이 경우에는 OXXOX가 정답이 된다.

 

그래서 무작정인 OXOXOX 혹은 XOXOXO는 안 되는 걸 발견하여 식을 검토하면서 생각해 봤다..

관찰해 보니 table[n][1]은 괜찮았지만, table[n][0]에서 최댓값이 유지가 안되고 있었다..!

 

예시 중에서도 [0 ,2, 1, 3] 이런 식으로 중간에 최댓값을 유지한다는 불변식이 깨져서 올바른 답이 도출이 안되고 있었다.

그래서 어떻게 해야 최댓값을 유지할 수 있을까 생각해 보았다.

 

이번차례에 선택을 하지 않았다고 해서 꼭 이전 차례에 선택된 값을 채용해할까?라는 생각이 들어서,

이전 차례에 선택하지 않은 값과 선택한 값 중에 더 큰 값을 채용하는 편이, 최댓값을 유지하는 방법이라고 생각했다.

table[n][0] = max(table[n - 1][0], table[n - 1][1]);
table[n][1] = table[n - 1][0] + nums[n];

 

추가로 table이 int형이 가능한지까지 확인 후 구현으로 들어갔다.

n의 최대 길이가 100이고 최대 값은 400이므로 OXOX...로 계산하면 $400 \times 50 = 20,000$이므로 int형으로 충분히 저장 가능하다.

 

 

구현

int rob(vector<int>& nums) {
    int table[101][2] = {0};
    table[0][1] = nums[0];

    int n = nums.size();

    for (int i = 1; i < n; ++i)
    {
        table[i][0] = std::max(table[i-1][0], table[i-1][1]);
        table[i][1] = table[i-1][0] + nums[i];
    }

    return std::max(table[n - 1][0], table[n - 1][1]);
}

 

 

되돌아보기

불변식이 깨져있는지조차 인지를 못했어서 시간이 더 소모됐었다.

불변식에 대해 더 신경 써야겠다.