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

1. 문제

코딩테스트 연습 - 도둑질 | 프로그래머스 (programmers.co.kr)

코딩테스트 연습 - 도둑질

2. dp - recursive

이 문제를 해결하려면 두 패턴을 비교해야한다.

 

첫 패턴은 0 에서부터 반복되는 패턴

 

두번째 패턴은 1에서부터 반복되는 패턴

 

두가지 패턴은 두 상황이 생긴다

 

현재 인덱스를 포함할 것인지

 

포함하지 않을 것인지

 

그리고 포함할 경우 다음 인덱스가 이전에 포함되어있으면 안된다

(순환할 경우 이런 경우가 생긴다. 이 경우는 첫 패턴에서만 생긴다)

 

이를 재귀적으로 작성한 코드는 다음과 같다.

 

#include <string>
#include <vector>
#include <cstring>
 
using namespace std;
 
int dp(int i, int start, vector<int>& money, int cached[1000000]) {
    if(i >= money.size())
        return 0;
    int& ret = cached[i];
    if(ret != -1)
        return ret;
    if((i + 1) % money.size() != start) {
        ret = dp(i + 2, start, money, cached) + money[i];
    }
    ret = max(ret, dp(i+1, start, money, cached));
    return ret;
}
 
int solution(vector<int> money) {
    int cached[2][1000000];
    memset(cached[0], -1, money.size()<<2);
    memset(cached[1], -1, money.size()<<2);
    return max(dp(0, 0, money, cached[0]), dp(1, 1, money, cached[1]));
}

3. dp -iterative

이 풀이는 i 를 1씩 증가시키면서

 

해당 원소를 포함하는 것과 포함하지 않는것 중 큰 값을 저장하여 문제를 해결해나간다.

 

 

일단 첫 번째 패턴인 첫원소를 가진 것 부터 살펴보면

 

i = 2는 첫 원소를 가지고 다음으로 가질 수 있는 원소이다.

 

그러므로 이 원소를 포함한 one[i-2] + money[i] 와 

 

포함하지 않은 one[i-1](money[0]) 중에 더 큰 원소를 one[i]에 넣는다.

 

그후 i를 1씩 증가하게 되면 자연스럽게 1칸 2칸 띄어넘는것 까지 고려하여 최대 값을 찾을 수 있게 된다.

 

 

두번째 패턴에서도 마찬가지로 동작한다

 

여기서 two[0] = 0으로 두어 i = 2 일때 3번째 원소부터 시작하는 경우와 2번째 원소부터 시작하는것 중

 

최댓값을 얻어 낼 수 있다.

#include <string>
#include <vector>
 
using namespace std;
 
int solution(vector<int> money) {
    vector<int> one(money.size(),money[0]), two(money.size(),money[1]);
 
    two[0] = 0;
 
    for(int i = 2 ; i <= money.size() - 1 ; i++) {
        if (i != money.size() - 1)
            one[i] = max(one[i-2] + money[i], one[i-1]);
    
        two[i] = max(two[i-2] + money[i], two[i-1]);
    }
    
    return max(one[money.size()-2],two[money.size()-1]);
}