[프로그래머스] 도둑질 (C++)

DP 동적프로그래밍

이런 배치로 되어있는 마을에서 각 집이 보유하고 있는 돈이 배열로 주어짐

누군가 이 집들을 털 계획을 하고 있는데, 두집을 연속으로 털지 못함 (!주의! 첫집과 끝집도 함께 털지 못함)

최대로 털 수 있는 금액을 반환하는 문제

 

접근방법

dp문제라서 작은 문제로 쪼개서 하면, dp배열에 i번째 인덱스에 저장되는 값은 i번째까지의 금액이다.

dp배열의 값을 입력하는 점화식은 아래와 같음

dp1[i] = max(dp1[i-1] , dp1[i-2]+money[i])

 

--> 바로 전 집까지의 최대값(바로 전 집이 포함되어 있을 수 있음) vs 두칸 전 집까지의 최댓값(i바로 전 집은 포함하지 않음) + 현위치의 집 금액

 

dp배열이 두개 필요한데, 이유는 첫집은 무조건 포함하고 끝집을 포함하지 않는 조건으로 계산하는 경우 dp1,

첫집을 포함하지 않는 조건으로 계산하는 경우 dp2

dp1배열은 끝집은 포함하지 않아야 하기 때문에 dp1[n-1] 값은 계산하지 않고 0으로 둔다.

dp1은 [0]이 money[0]이고 (첫집을 무조건 포함하기 때문)

dp2는 [0]이 0이다. (첫집을 제외하고 계산하기 때문)

 

점화식으로 dp배열의 값이 입력되는 과정은 위의 그림과 같다.

 

https://velog.io/@imacoolgirlyo/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EB%8F%84%EB%91%91%EC%A7%88-%ED%8C%8C%EC%9D%B4%EC%8D%AC

[프로그래머스] 도둑질, 파이썬

이 블로그 참고해서 풀었다.

 

소스코드

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

using namespace std;

int solution(vector<int> money) {
    int answer = 0;
    int n = money.size();
    
    vector<int> dp1(n, 0);
    dp1[0] = money[0];
    dp1[1] = max(money[0], money[1]);
    for(int i = 2 ; i < n-1 ; i++){
        dp1[i] = max(dp1[i-1], dp1[i-2] + money[i]);
        if(answer < dp1[i]){
            answer = dp1[i];
        }
    }
    vector<int> dp2(n, 0);
    dp2[0] = 0;
    dp2[1] = money[1];
    for(int i = 2; i < n ; i++){
        dp2[i] = max(dp2[i-1], dp2[i-2] + money[i]);
        if(answer < dp2[i]){
            answer = dp2[i];
        }
    }
    
    return answer;
}