프로그래머스 : 저울

맨 처음에 탐욕법이라길래 모든 경우의 수를 구했는데,,, 역시나 시간초과가 날것 같았다.

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

using namespace std;
vector<int> w;
vector<bool> v;
bool dfs(int num,int sum){
    if(num<sum){
        return false;
    }
    if(num==sum){
        return true;
    }
    for(int i=0; i<w.size(); i++){
        if(w[i]>num) continue;
        if(v[i]==false){
            v[i] = true;
            if(dfs(num,sum+w[i])){
                for(int i=0; i<v.size(); i++){
                    v[i] = false;
                }
                return true;
            }
            v[i] = false;
        }
    }
    return false;
}

int solution(vector<int> weight) {
   // sort(weight.begin(), weight.end());
    w=weight;
    v.resize(w.size(),false);
    int answer = 0;
    int max_value = accumulate(weight.begin(),weight.end() ,0);
    for(int i=1; i<max_value; i++ ){
        if(find(weight.begin(),weight.end(),i)!=weight.end()) continue;
        if(!dfs(i,0)) {
            answer=i;
            return answer;
            break;
        }
    }
    answer = max_value+1;
    return answer;
}

---

풀이 :

1 1 2 3 6 7 30

 

(앞의 모든 합의 +1)이  다음 숫자보다 작다면 최소 불가능한 수는 앞의 모든합 +1 이다.....

 

이게 이해는 잘 안가지만,,, 해보면 그렇다 . 이해가 간다.

 

정말 이 문제 만든사람은 똑똑한거 같다.

 

테스트 케이스

1 1 3 --> 답은 6 

 

먼저 첫 원소 1 의 +1 은 2

2는 1보다 크다

그다음 첫번째 두번째 원소의 합 2 +1 은 3

3은 3이랑 같다.

그다음 첫번째 두번째 세번째 원소의 합 5

그래서 마지막 6를 나타낼수 없다.

 

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

int solution(vector<int> weight) {
    int answer = 0;
    sort(weight.begin(), weight.end());
    answer+=weight.front();
    for(int i=1; i<weight.size(); i++){
        if(answer+1<weight[i]) break;
        answer+=weight[i];
    }
    return answer+1;
}