JArchive 프로그래밍 일기

도둑질 문제 링크 

리뷰 

인접한 두 집을 털면 경보가 울린다. 따라서 한 개 건너서 털어야 한다. 

집이 동그랗게 이어져있으니까, 첫번째 집을 털면 마지막 집은 털 수 없다. 

마지막 집을 털면 첫번째 집은 털 수 없다. 이걸 구분해서 DP 배열을 만들어야한다. 

첫 번째 집을 턴다 (== 마지막 집 못 턴다)

마지막 집을 턴다 (== 첫번째 집 못 턴다)

"맞았습니다"코드

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

int D1[1000001]; // 첫번째 집을 턴다
int D2[1000001]; // 첫번째 집 안털고, 마지막 집을 턴다.

int solution(vector<int> money) {
  int answer = 0;
  int msize = money.size();

  D1[0] = money[0]; // D1: 첫번째 집을 턴다.
  D1[1] = max(money[0], money[1]);

  D2[0] = 0;        // D2: 마지막 집을 턴다.
  D2[1] = money[1];

  for(int i = 2; i < msize-1 ; i++) { // 첫번째 집을 터니까 msize-2 까지 반복.
    D1[i] = max(D1[i-2] + money[i], D1[i-1]);
  }
  for(int i = 2; i < msize; i++) { // 마지막 집을 터니까 msize-1 까지 반복.
    D2[i] = max(D2[i-2] + money[i], D2[i-1]);
  }
  answer = max(D1[msize-2], D2[msize-1]);
  return answer;
}