[프로그래머스/C++] 도둑질

 

 

문제

문제 설명

 

 

 

풀이

 

 

이 문제는 완전 탐색과 같이 풀기에는 힘든 문제다.

만약 완전 탐색으로 풀 경우를 예로 들면 첫 번째 집을 털경우 세번째 집을 털거나 안털거나 경우로 나뉠텐데, 이런식으로 계산하다보면 2^n과 같은 지수형태의 시간 복잡도를 가지게 되기 때문이다.

 

그래서 문제를 풀기 위해서는 이전에 계산한 값들을 갱신하면서 경우의 수를 줄여 주는게 핵심이다.

 

1. 만약 바로 직전에 붙어있던 집을 도둑질 했을 경우 현재 집은 도둑질 할 수 없다. 

2. 바로 직전에 붙어있던 집을 도둑질 했을 경우 현재 집은 도둑질하거나 하지 않을 수 있다.

 

위 두 조건을 생각하면 현재 집까지 도둑질 했을 때 돈의 최댓값은 다음과 같이 나타낼 수 있다.

 

1. [바로 직전 집을 도둑질 하지 않았을 경우의 최댓값] + [현재 집을 도둑질 할 경우

2. [바로 직전 집을 도둑질 했을 경우의 최댓값]

 

위 두 경우를 비교하며 마지막 집까지 탐색을 한 후 최댓값을 return하면 된다.

 

여기서 예외 조건이 하나 있는데 집들은 원형으로 배치되어 있으므로, 처음집을 도둑질 할 경우, 마지막 집은 도둑질을 할 수 없다는 점이다.

 

그러므로 처음 집을 도둑질 하고 마지막집을 도둑질 하지 않는 경우,

처음 집을 도둑질 하지 않고 마지막집을 도둑질 하는 경우로 나눠서 계산을 해준 다음 최댓값을 구하면 된다.

​

[아이디어 정리]

1. 바로 직전의 집을 도둑질하는 경우와 도둑질 하지 않는 경우로 나눠 매 집마다 최댓값을 누적하며 구한다.
2. 처음 집을 도둑질하는 경우와 도둑질 하지 않는 경우로 나눠 최댓값을 구한다.

 

 

 

Code

 

 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int solution(vector<int> money) {
    int answer = 0;
    // 처음 집이 털리고 마지막 집이 안털리는 경우
    vector<int> prevSelect(money.size(),0) ,prevNotSelect(money.size(),0);
    prevSelect[0]=money[0];
    for (int i=1; i<money.size()-1; i++)
    {
        prevNotSelect[i]=max(prevNotSelect[i-1],prevSelect[i-1]);
        prevSelect[i]=prevNotSelect[i-1]+money[i];
    }
    answer=max(prevSelect[money.size()-2],prevNotSelect[money.size()-2]);
    // 처음 집이 안털리고 마지막 집이 털리는 경우
    prevSelect=vector<int>(money.size(),0), prevNotSelect=vector<int>(money.size(),0);
    for (int i=1; i<money.size(); i++)
    {
        prevNotSelect[i]=max(prevNotSelect[i-1],prevSelect[i-1]);
        prevSelect[i]=prevNotSelect[i-1]+money[i];
    }
    answer=max({prevSelect[money.size()-1],prevNotSelect[money.size()-1],answer});
    return answer;
}

 

---

 

요즘 이런 유형의 문제가 나오면 DP 문제라는게 눈에 보여 쉽게 풀린다

 

 

프로그래머스