[Programmers] 저울

문제 출처 :

 

https://programmers.co.kr/learn/courses/30/lessons/42886

 

 

 

알고리즘 분석 :

문제 해결에 필요한 사항

1. Greedy

 

작은 추들부터 누적 합을 더해가며 현재 누적합 + 1보다 현재 추의 무게가 크다면

 

이전의 추들을 모두 합쳐서도 현재 추를 만들어 낼 수 없다는 의미가 되기에 해당 추는 만들어 낼 수 없다는 것이 된다.

 

따라서 해당 추는 만들 수 없지만, 그 중 만들 수 없는 추의 최소 크기는 누적합 + 1이 된다.

 

 

 

 

 

소스 코드 : 

 

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

using namespace std;

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