[프로그래머스] 도둑질

문제 주소 : programmers.co.kr/learn/courses/30/lessons/42897

코딩테스트 연습 - 도둑질

문제 확인

 

dp문제

처음 집을 선택하는가에 따라 2가지 스텝으로 분류합니다.

 

풀이

 

처음 집을 선택한 경우 마지막 집을 선택할 수 없으므로 size -1 까지 탐색을 합니다. 선택하지 않은 경우는 size 까지 모두 탐색을 합니다.

n개의 배열을 둘 필요없이 2칸 단위로 잘라 최댓값을 지정하기 위해 3칸의 배열을 사용합니다.

현재 집을 털었을 때 비용과 털지 않고 옆집으로 이동 했을 때를 비교하여 선택하며 진행해 갑니다.

마지막에 두 경우중 큰 값을 선택합니다.

 

코드

#include <string>
#include <vector>
 
using namespace std;
 
int solution(vector<int> money) {
    int answer = 0;
    int dp[3] = { money[0], money[0] };
    for (int i = 2; i < money.size() - 1; i++) {
        int t = dp[0] + money[i];
        dp[2] = dp[1] > t ? dp[1] : t;
        dp[0] = dp[1]; dp[1] = dp[2];
    }
    answer = dp[2];
 
    dp[0] = 0; dp[1] = money[1];
    for (int i = 2; i < money.size(); i++) {
        int t = dp[0] + money[i];
        dp[2] = dp[1] > t ? dp[1] : t;
        dp[0] = dp[1]; dp[1] = dp[2];
    }
 
    return answer > dp[2] ? answer : dp[2];
}
int main() {
 
    vector<int> money = { 1, 2, 3, 1 };
    solution(money);
}