[백준][C++] 2437 저울

 

 

 

알고리즘 종류

    - 탐욕

    - 정렬

 

 

사고 과정

    - 아무 생각이 없다...

    - 방법을 찾아보자

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

        2. 추에서 무게가 1인 추가 없으면 무게 1을 만들 수 없다.

        3. 추의 무게를 오름차순으로 누적할 때, sum(누적합)+1보다 다음 추의 무게가 크다면 sum+1 무게를 만들 수 없다. 이 블로그의 도움을 받았습니다. 깔끔한 설명이 있습니다.

            3-1. sum의 의미: 1부터 sum까지 무게를 만들 수 있다는 의미이다. 아래 그림을 보자. sum이 4일 때, (4 = 2+1+1), (3 = 2 + 1)로 만들 수 있다. sum이 13일 때, (12 = 6+3+2+1), (11 = 6+3+2), (10 = 6+3+1), ... 만들 수 있다.

            3-2. sum + 1 < 입력 값의 의미: sum이 20일 때는 20까지 측정할 수 있습니다. 이 때, 다음 추의 무게가 21이면 21 + sum이 되어서 41까지 측정 가능합니다. 그런데 21을 건너뛴 22가 나온다면, 21은 측정할 수 없습니다. 그래서 위와 같은 식이 나왔습니다.

 

 

 

구현(C++)

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int n;
vector<int> v;
 
int main(void){
    cin >> n;
    
    int num;
    for(int i=0; i<n; i++){
        cin >> num;
        v.push_back(num);
    }
    
    sort(v.begin(), v.end());
    
    // 1이 없다면, 1을 만들 수 없다.
    if(v[0] != 1){
        cout << 1 << endl;
        return 0;
    } 
    
    int sum = v[0];
    for(int i=1; i<n; i++){
        // 누적 합 + 1 < 비교 값이 성립하면, 누적합 + 비교 값까지 만들 수 있다.
        if(v[i] > sum +1){
            cout << sum + 1 << endl;
            return 0;
        }
        sum += v[i];
    }
    cout << sum + 1 << endl;
    return 0;
}

 

 

 

시행착오

    - 이전에 이분탐색을 배웠었다. 그래서 이분탐색을 적용해보기로 했다. for문으로 1~추의 총 무게까지 반복하면서, 확인 가능한 추의 무게를 a라고 하면, a이하의 추들 중에서 가장 큰 것을 골라서 빼주는 방법을 했다. 그래서 결과가 0이 나오면, a는 확인 가능한 무게이고, 아니면 확인 불가능하다. 그런데 시간초과가 나와서 다른 방법을 찾아보았다.