[프로그래머스] 도둑질

문제 설명

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

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

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

 

제한사항

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

---

C++ 풀이

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

int solution(vector<int> money) {
	vector <long> one;
	vector <long> two;
	int msize = money.size();
	one.resize(msize, money[0]);
	two.resize(msize, money[1]);
	two[0] = 0;
	for (int i = 2; i <= msize - 2; i++)
		one[i] = max(one[i - 2] + money[i], one[i - 1]);
                            
	for (int i = 2; i <= msize - 1; i++)
		two[i] = max(two[i - 2] + money[i], two[i - 1]);

	return max(one[msize - 2], two[msize - 1]);
}

• 첫번째 집부터 훔치는 경우
• 두번째 집부터 훔치는 경우

위 두 가지 상황으로 나눠서 실행

 

현재 도둑질하려는 집의 돈 + (현재집 -2)집의 돈    vs     (현재집 -1)집의 돈

비교하여, 더 큰 값을 저장

 

 

문제 링크

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

코딩테스트 연습 - 도둑질 | 프로그래머스