[프로그래머스] 도둑질

https://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

 

풀이

해당 문제풀이는 다음과 같이 2가지의 형태로 나뉘어 진다.

1) 첫번째 집부터 털었을 때 : dp 이름의 배열을 만든다.

2) 두번째 집부터 털었을 때 : dp2 이름의 배열을 만든다.

 

다만 vector의 사이즈와 Index는 차이가 있어 헷갈렸는데 이 부분 주의 할 것.

 

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int max(int a, int b){
    
    return a>b ? a:b;
}
int solution(vector<int> money) {
  
    int houseNum = money.size();
    int dp1[1000000]; //첫번째 집 털었을 때.
    int dp2[1000000]; //두번째 집 털었을 때.
    
    dp1[0] = money[0];
    dp1[1] = money[0];
    dp1[2] = max(dp1[1],dp1[0]+money[2]);
    dp1[3] = max(dp1[2], dp1[1]+money[3]);
    //첫번째 집부터 털어보자.
    for(int i=2; i<houseNum-1;i++){
        
        dp1[i] = max((dp1[i-2] +money[i]),dp1[i-1]);
    }
    
    dp2[0] =0;
    dp2[1] = money[1];
    
    dp2[2] = max(money[2]+dp2[0], dp2[1]);
    dp2[3] = max(dp2[1]+money[3], dp2[2]);
    
    //두번째 집부터 털어보자.
    for(int j=2; j<houseNum;j++){
        dp2[j] = max((money[j]+dp2[j-2]),dp2[j-1]);
    }
    
    return max(dp1[houseNum-2],dp2[houseNum-1]);
}

 

최종적으로 dp1과 dp2의 마지막 Index값을 비교하여 둘 중 큰 값을 정답으로 return한다.