[DP] 도둑질

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

코딩테스트 연습 - 도둑질

 

문제 설명

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

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

각 집에 있는 돈이 담긴 배열 money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최댓값을 return 하도록 solution 함수를 작성하세요.

제한사항

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

입출력 예

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

 

---

 

Sol) DP

1. 나올 수 있는 case

- 첫번째 값을 포함하는 경우 - dp1

- 첫번째 값을 포함하지 않는 경우 - dp2

2. dp1과 dp2에는 해당 index에서 가질 수있는 최대값 저장

- i-2 인덱스의 값+현재값, 현재 최대값중 더 큰 것 

3. dp1의 최대값과 dp2의 최대값 중 더 큰게 answer

- 마지막 index에 가장 큰 값을 가지고 있다.

#include <iostream>
#include <vector>

using namespace std;

int solution(vector<int> money) {
    int answer = 0;
    vector<int> dp1;
    vector<int> dp2;
    
    // 첫번쨰 값 선택 ㅇ
    dp1.push_back(money[0]);
    dp1.push_back(money[0]);
    for(int i=2; i<money.size()-1; i++){
        dp1.push_back(max(dp1[i-2]+money[i], dp1[i-1]));
    }
    
    // 첫번쨰 값 선택 x
    dp2.push_back(0);
    dp2.push_back(money[1]);
    for(int i=2; i<money.size(); i++){
        dp2.push_back(max(dp2[i-2]+money[i], dp2[i-1]));
    }
        
    answer = max(dp1[dp1.size()-1], dp2[dp2.size()-1]);
    return answer;
}