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

문제 

programmers.co.kr/learn/courses/30/lessons/42897

코딩테스트 연습 - 도둑질

도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다.

각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 두 집을 털면 경보가 울립니다.

각 집에 있는 돈이 담긴 배열 money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최댓값을 구해보자! 

 

제한사항

• 이 마을에 있는 집은 3개 이상 1,000,000개 이하입니다.
• money 배열의 각 원소는 0 이상 1,000 이하인 정수입니다.

입출력 예

money	return
[1, 2, 3, 1]	4

풀이

DP를 활용해서 풀이하였다. 

cache[i] : 시작점 ~ i 까지 돌았을 때, 훔칠 수 있는 최대 money

cache[i] = max (cache[i-1], money[i] + cache[i-2]) 또는, 

cache[i] = max (cache[i+1], money[i] + cache[i+2]) 로 계산할 수 있다.

바로 옆의 집을 선택하느냐, 현재 집과 그 옆옆집을 선택하느냐 중에 더 큰 것을 고르는 셈이다.

 

문제 조건에 집들이 동그랗게 배치되어 있다고 했으나, 실제 코드에서는 일차원 배열 or 벡터로 사용되므로 

이 문제는 크게 세 가지 경우로 나누어볼 수 있다. 

(배열에서의 시작점과 끝 집을 모두 털 수 없기 때문이다)

 

1. 첫번째 집을 털고, 마지막 집을 안 터는 경우 

2. 첫번째 집을 안털고, 마지막 집을 터는 경우

3. 첫번째 집, 마지막 집 모두 안 터는 경우 

왼쪽부터 1,2,3 case

 

1번 case (첫집 O, 마지막집 X)	2번 case (첫집 X, 마지막집 O)	3번 case (첫집 X, 마지막집 X)

세 가지 case 중에 최댓값은 첫 번째, 두번째 case의 9이다. 따라서 답은 9이다. 

코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;



int solution(vector<int> money) {
	int answer = 0;
	int n = money.size();
    vector<int> cache(n);
	// 무조건 첫집 O, 마지막 집 X
    cache[0] = money[0];
    cache[1] = money[0]; 
    for (int i=2;i<n-1;i++){
        cache[i] = max(cache[i-1], money[i]+cache[i-2]);
    }
    answer = *max_element(cache.begin(),cache.end());
    
    // 첫집 X, 마지막집 0
    fill(cache.begin(),cache.end(),0);
    cache[n-1] = money[n-1];
    cache[n-2] = money[n-1];
    for (int i=n-3;i>0;i--){
        cache[i] = max(cache[i+1], money[i]+cache[i+2]);
    }
    answer = max(answer, *max_element(cache.begin(),cache.end()));
    //둘다 X
    fill(cache.begin(),cache.end(),0);
    cache[1] = money[1];
    for (int i=2;i<n;i++){
        cache[i] = max(cache[i-1], money[i]+cache[i-2]);
    }
    answer = max(answer, *max_element(cache.begin(),cache.end()));
	return answer;
}

결과