[C++]백준(BOJ) 2473 - 저울 (그리디)

 

난이도 : 골II

풀이 시간 : 40분

알고리즘 유형 : 그리디, 정렬

풀이 방법 : 오름차순의 합을 구한 뒤 비교 

 

 

문제 예시

무게가 양의 정수인 N개의 저울추가 주어질 때, 이 추들을 사용하여 측정할 수 없는 양의 정수 
무게 중 최솟값을 구하는 프로그램을 작성하시오.

예를 들어, 무게가 각각 3, 1, 6, 2, 7, 30, 1인 7개의 저울추가 주어졌을 때, 
이 추들로 측정할 수 없는 양의 정수 무게 중 최솟값은 21이다. 

입력
첫 째 줄에는 저울추의 개수를 나타내는 양의 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 
둘째 줄에는 저울추의 무게를 나타내는 N개의 양의 정수가 빈칸을 사이에 두고 주어진다. 
각 추의 무게는 1이상 1,000,000 이하이다.

출력
첫째 줄에 주어진 추들로 측정할 수 없는 양의 정수 무게 중 최솟값을 출력한다.

 

 

문제 풀이

처음에 N = 1000 이기 때문에 완전탐색으로 풀어야지 싶었는데 시간초과가 나왔습니다.
(난이도를 가려놓고 풀어서..)

 

그래서 다시 보니 추를 계산하는 탐욕적인 방법이 존재했습니다.

즉, 이 문제는 그리디 알고리즘을 사용하여 풀 수 있습니다.

아이디어

1. 측정 가능한 최대 무게를 관리하는 변수 max_weight 를 설정합니다. 초기값에 1이 없다면
   1을 측정할 수 없기 때문에 1을 출력하고, 1이 있다면 초기값은 1로 설정합니다.
   
   ★ 이유: max_weight는 현재까지 추들로 만들 수 있는 모든 무게의 합의 범위를 나타냅니다.
        예를 들어, max_weight = 5라면 1부터 5까지 모든 무게를 측정할 수 있음을 의미합니다.
   
   
2. 입력받은 추의 무게를 오름차순으로 정렬합니다.
   
   ★ 이유: 작은 추부터 차례로 더해가며 확인하면,측정 불가능한 최소 무게를
        빠르게 찾을 수 있습니다.
   
   
3. 현재 추의 무게 v[i]이 max_weight + 1보다 크다면, 측정할 수 없는 최소 무게는
   max_weight + 1입니다.
   
   ★ 이유:  max_weight + 1보다 작은 무게는 이미 측정 가능하므로,
        이 범위를 벗어나는 순간이 최소값입니다.
   
   
4. 그렇지 않다면, 현재 추의 무게를 max_weight 에 더해 측정 가능한 범위를 확장합니다.
5. 모든 추를 확인한 후, 마지막으로 max_weight  +1을 출력합니다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n, m, k;

int main() 
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;

    vector<int> v(n);

    for(int i = 0; i < n; ++i)
        cin >> v[i];
   
    sort(v.begin(), v.end());

    if (v[0] != 1)
    {
        cout << 1;
        return 0;
    }

    int max_weight = 1;

    // 7 1 1 2 3 8 10 12(반례 찾기)
    
    // 1 1 2 3 6 7 30
    for (int i = 1; i < n; ++i)
    {
        // 부분합으로 계산
        if (max_weight + 1 < v[i])
            break;

        max_weight += v[i]; // 2 4 7 13 20
    }

    // 구할수 있는 최대 증량 + 1 == 구할 수 없는 증량
    cout << max_weight + 1;

    return 0;
}