[프로그래머스 :: DP] 도둑질

programmers.co.kr/learn/courses/30/lessons/42897

코딩테스트 연습 - 도둑질

 i번째 집을 방문하면 i-1번째 집을 방문할 수 없고 i-2번째 집을 방문할 수 있다. i번째 집을 방문하지 않으면, i-1번째 집을 방문할 수 있다. 배열을 만들어, 도둑이 집을 방문하며 얻은 최대값을 저장하면된다. 이때 i번째 집은 방문 하거나 방문 하지 않거나 선택할 수 있다. 최대값을 반환하면 되므로 다음과 같은 식을 세울 수 있다.

 

i번째 최적값은 (i-2번째 최적값 + i번째 집이 가지고 있는 돈)과 (i-1번째 최적값) 중 큰 값  

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

 

 이 때 0번째 집을 털면 마지막 집을 털 수 없다. 따라서 첫 번째 집을 털었을 때 결과값은 마지막 집의 최적값이 아니라 마지막 전 집의 값이다.

  0번째 집을 털지 않으면 마지막 집을 털 수 있으므로, 마지막 값이 최적값이다. 2가지 케이스를 나눌 수 있다.

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

int solution(vector<int> money) {
    vector<int> from0(money.size(),0);
    vector<int> from1(money.size(),0);    
    
    // 0번째를 방문하였으므로 1번째와 마지막은 방문불가능하다.
    from0[0] = money[0];
    from0[1] = money[0];
    
    // 0번째 방문하지 않았으므로 1번째와 마지막은 방문가능하다.
    from1[0] = 0;
    from1[1] = money[1];
    
    for(int i=2; i<money.size(); ++i ){
        from0[i] = max( from0[i-2]+ money[i] , from0[i-1] );
        from1[i] = max( from1[i-2]+ money[i] , from1[i-1] );        
    }
    return max(from0[money.size()-2], from1[money.size()-1]);   
}

 문제를 보고 점화식을 어떻게 만들지 떠오르지 않아, 내 나름대로 풀어버렸다. 그리고 틀렸따. 실전에선 어떤 카테고리에 속한 문제인지 나오지 않기 때문에, 아래와 같이 문제를 풀이하다 많은 시간을 보내고, 정답도 못 맞출 가능성이 높다. 문제를 보고 어느 카테고리에 속해있는지 판단하는 일이 첫 번째다.

 어떻게 접근을 해야할까? 문제에서 규칙을 찾은 다음에 이 규칙을 코드에 적용하려면 어떻게 해야하는지 생각하는 편이다. 동적계획법은 이전에 찾은 최적값을 그 다음 번에 사용할 수 있는데, 그러한 규칙을 찾지 못했기 때문에 동적계획법으로 풀지 못했다. 

 

틀린풀이

가장 큰 값을 뽑아, 좌우 합친 값보다 더 크면 좌우 값을 버리고 뽑은 값 보다 좌우 합친 값이 더 크면 뽑은 값을 버렸다. 버리는 값을 0으로 표기해주면 된다. 

#include <string>
#include <vector>
#include <utility>
#include <iostream>
#include <algorithm>
using namespace std;


bool compare(pair<int,int> p1, pair<int,int> p2){
    return p1.first<p2.first;
}

int solution(vector<int> money) {
    vector<pair<int,int>> v;
    for(int i=0; i<money.size(); ++i)
        v.push_back(make_pair(money.at(i),i));
    
    sort(v.begin(),v.end(),compare);
    
    while(!v.empty()){
        pair<int,int> curr = v.back(); v.pop_back();
        int idx = curr.second;

        int left = idx-1; 
        int right = idx+1;
        if(left==-1){ left = money.size()-1; }
        if(right==money.size()){ right = 0; }

        if(money[idx]!=0){
            if(money[left] + money[right] > money[idx]){
                money[idx]=0;
            }else{
                money[left] = 0; money[right] =0;
            }
        }
    }
    int sum = 0;
    for(int i:money)
        sum+=i;
    return sum;
}

 예외 { 41, 67, 134, 100, 169, 124, 78, 158, 162, 64 }

 위 로직을 따라가면 가장 큰 값은 169를 처음으로 뽑는다. 그리고 좌우 값을 비교한다. 124 +100이 더 크므로 169를 버린다. 최대값이 나오는 정답은 { 41 0 134 0 169 0 78 0 162 0 }을 선택한 경우이다. 169를 포함하고 있다.

 이 문제를 해결하기 위해 169 값 옆자리에 0을 넣어버리면 169를 항상 포함하게 된다. solution의 기능을 function으로 복붙한 다음 solution에서 index를 function으로넘기면서 Forloop를 돈다. function 안에서는 index으로 넘겨받은 값을 0으로 만들어 버리면 된다. 그러면 169값을 사용할 수 있다. 금방 구현할 수 있는데 문제가 또 생긴다. 그 다음 큰 값인 162를 사용해야 하는데, 위 로직을 사용하면 158+64가 더 크므로 162을 씹어버린다. 이를 또 해결하려면 solution에서 0으로 초기화 하는 index를 한개만 넘기는게 아니라 여러개 넘겨서 모든 경우의 수를 순회해야 한다. 

 따라서 solution에서 몇 개의 값을 초기화 할 지 forloop를 만들어 순회한다. 한 개를 초기화 할 때는 순서대로 하면 되고 2개 일 때는 한칸이상 떨어지게 해서 모든 경우의 수를 시도한다. 3개 일 때도 각각 한 칸 이상 떨어지게 해서 모든 경우의 수를 시도한다. 초기화 개수를 number 개수의 절반까지만 시도하면 된다.  시도한 경우 중 최대값을 반환하면 끝.

 

 위 방법으로 코드를 짜기가 복잡해서 간단하게 combination을 사용했다. 0,1,2,,,,size-1까지 배열에 넣어준 후 중복되지 않는 모든 조합을 2차원 배열에 넣어준다. 이 배열은 삭제할 값의 idx를 나타낸다. 문제 조건은 연속해서 삭제할 때 최댓값을 구할 수 없으므로 필요없다. 연속해서 삭제하는 경우와 처음과 끝을 동시에 삭제하는 경우를 제외시켜준다.

#include <string>
#include <vector>
#include <utility>
#include <iostream>
#include <algorithm>
using namespace std;

// Combination
vector<vector<int>> combi_Saved;
vector<int> vC = { 1,2,3,4,5 };
int len = vC.size();
vector<int> sub;

void combination(int k) {

    if (k == len  ) {
        combi_Saved.push_back(sub);
    }
    else {
        sub.push_back(vC[k]);
        combination( k + 1);
        sub.pop_back();
        combination( k + 1);
    }
}
/////////////////////////////////////////


void print2D(string s, vector<int>v){
    cout << s << "={ ";
    for(int i:v)
        cout << i << " ";
    cout << "}";
}

bool compare(pair<int,int> p1, pair<int,int> p2){
    return p1.first<p2.first;
}

int utility(vector<int> money, vector<int> deleting){
    vector<pair<int,int>> v;

    for(int i:deleting)
        money.at(i) = 0;

    for(int i=0; i<money.size(); ++i)
        v.push_back(make_pair(money.at(i),i));
        
    sort(v.begin(),v.end(),compare);
    
    while(!v.empty()){
        pair<int,int> curr = v.back(); v.pop_back();
        int idx = curr.second;

        int left = idx-1; 
        int right = idx+1;
        if(left==-1){ left = money.size()-1; }
        if(right==money.size()) right = 0; 

        if(money[idx]!=0){
            if(money[left] + money[right] > money[idx]) money[idx]=0;
            else money[left] = 0; money[right] =0;
        }
    }
    int sum = 0;
    for(int i:money)
        sum+=i;
    return sum;
}

int solution(vector<int> money) {
    vC.clear();
    for(int i=0; i<money.size(); ++i){
        vC.push_back(i);
    }
    len = vC.size();
    combination(0);

    // delete consequential Number
    for(int i=0; i<combi_Saved.size(); ++i){
        int size = combi_Saved[i].size();
       for(int j=1; j<size;++j)
           if(combi_Saved[i][j]==combi_Saved[i][j-1]+1 ||
           combi_Saved[i][0]==0 && combi_Saved[i][size-1]==money.size()-1)
                combi_Saved[i].clear();
    }
    vector<vector<int>> combi;
    for(const auto& a:combi_Saved){
        if(!a.empty()) combi.push_back(a);
    }
    for(const auto& a:combi){
        print2D("after",a);
        cout << endl;
    }
    
    int max = 0;
    for(const auto& deleting:combi){
        int temp = utility(money, deleting);
        if(temp>max) max = temp;
    }
    return max;
}

int main(){
    // 답 { 41 0 134 0 169 0 78 0 162 0 }
    vector<int> v = {41, 67, 134, 100, 169, 124, 78, 158, 162, 64 };
    int Asump = solution(v);
    cout << "Asumption=" << Asump << endl;    
}

 시간 초과라서 테스트 케이스로 직접 확인해봐야한다.... 정확도 테스트를 해봐야하는데......

 

콤비네이션 godog.tistory.com/entry/C-%EC%A1%B0%ED%95%A9Combination-%ED%9A%8C%EA%B7%80%EB%A5%BC-%EC%9D%B4%EC%9A%A9

C++ 조합(Combination) 회귀를 이용

 이걸로 코딩테스트 고득점kit 문제를 모두 풀었다. 레벨5 한 문제는 나중에 풀기로 하고. 이제 어느 정도 구현은 할만하다. 이제 구현보다 어떤 아이디어가 문제를 푸는 실마리가 되는지, TimeComplexity와 SpaceComplexity는 어떤지, STL이 내부적으로 어떻게 작동하는지에 집중해야겠다.