[프로그래머스] 저울

문제

저울추가 담긴 배열 weight가 매개변수로 주어질 때, 이 추들로 측정할 수 없는 양의 정수 무게 중 최솟값을 return 하도록 solution 함수를 작성해주세요.예를 들어, 무게가 각각 [3, 1, 6, 2, 7, 30, 1]인 7개의 저울추를 주어졌을 때, 이 추들로 측정할 수 없는 양의 정수 무게 중 최솟값은 21입니다.

제한 사항

• 저울추의 개수는 1개 이상 10,000개 이하입니다.
• 각 추의 무게는 1 이상 1,000,000 이하입니다.

입출력 예

weight	return
[3, 1, 6, 2, 7, 30, 1]	21

풀이)

dfs을 이용해서 나올 수 있는 모든 추의 무게조합을 보면, 시간초과가 나는 문제이다.

가장 무게가 적은 추부터 올려가며 누적값을 이용해 잴 수 없는 무게를 찾아내면 된다.

풀이과정

1. 추의 무게들을 오름차순으로 정렬한다.

2. 모든 추들을 작은 무게부터 누적값을 구한다.

   (만약, 누적값보다 큰 무게의 추가 있을 시, 거기서 누적 값 구하는것을 stop하고 어느 값까지 누적값이 이뤄졌는지 

    확인하여 그 다음 값을 return 한다.)

풀이과정을 읽으면 잘 이해가 되지 않을 것 같아 예시로 설명하겠다.

문제 예시) weights = [3,1,6,2,7,30,1]

이를 오름차순으로 정렬하면 [1,1,2,3,6,7,30]

첫번째 추부터 누적해보자. 

첫번째 원소는 1     누적값: 1 =>이는 1까지 추로 나타낼수 있다는 점

두번째 원소는 1     누적값: 2

세번째 원소는 2     누적값: 4 => 4까지 즉 1,2,3,4는 추로 만들수 있다는 점

네번째 원소는 3     누적값: 7 => 1,2,3,4,5,6,7을 추로 만들 수 있다는 점.

다섯번째 원소는 6    누적값: 13 

여섯번째 원소는 7    누적값: 20

일곱번째 원소는 30    *누적값 + 1 즉 21보다 큰 값이 나타남. 

  1~6번째 모두 더한 값 + 1보다 크다는 건 1~6번째 어느 원소와 조합해도 누적값 20 다음 숫자인 21이 절대 나올 수 없다는 것이다. 

따라서 나타낼 수 없는 최소값은 21

코드)

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

int solution(vector<int> weight) {
    sort(weight.begin(),weight.end());

    if(weight[0] > 1) return 1;

    int tmp = weight[0];
    for(int i=1;i<weight.size();i++){
        if(weight[i] > tmp + 1) break;
        tmp += weight[i];
    }
    return tmp + 1;
}