[BOJ 2437] 저울

[문제] : https://www.acmicpc.net/problem/2437

2437번: 저울

 

[개념]

- 그리디 (Greedy) 알고리즘

 

[풀이]

아이디어만 떠올린다면 생각보다 쉬운 문제이다. 

N개의 추가 주어졌을 때, 추들을 이용하여 측정할 수 없는 무게 중 가장 작은 무게를 구하는 것이다. 

첫 번째로, 측정할 수 있는 무게들을 모두 구하는 것은 당연히 풀이의 의도가 아니라는 것을 알 수 있어야 한다. 

완전 탐색으로 구한다고 한다면 추의 개수가 최대 1000개이므로 경우의 수가 최대 2의 1000승이 나오게 되고, dp 배열로 구한다고 하더라도, 추의 무게가 100만 이하이기 때문에 배열의 크기가 너무 커지기 때문이다.

반면, 쉽게 알 수 있는 부분은 추의 무게가 모두 양수이기 때문에 사용 가능한 추가 늘어날수록 측정할 수 있는 무게의 범위가 커진다는 것이다. 

이는 결국 측정할 수 없는 무게의 최솟값이 커질 '수' 있다는 것과 같은 의미이다. 

따라서 추의 무게들을 오름차순으로 정렬한 뒤, 추를 하나씩 체크하면서 측정불가능한 무게의 최솟값을 키워나간다. 

 

만약 k개까지 추를 추가했을 때 측정불가능한 무게의 최솟값이 m이라면, 이는 1 ~ m-1 의 무게를 모두 측정 가능하다는 의미이므로 무게가 M (<= m)인 k+1번째 추를 추가한다면 1 ~ m-1 + M 의 무게가 모두 측정이 가능해진다. 

따라서 k+1번째 추까지 추가하면 측정불가능한 무게의 최솟값은 m+M이 된다. 

만약에 M이 m보다 크다면 k+1번째 추를 추가하더라도 m이라는 무게는 측정이 불가능하며, 추가 오름차순으로 정렬되어있기 때문에 그 뒤의 추를 추가해도 m은 여전히 측정이 불가능하다. 그러므로 답이 m이 된다. 

 

[소스코드]

 

int main(void) {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int N; cin >> N;
    vector<int> v;
    for (int i = 1; i <= N; i++) {
        int a; cin >> a;
        v.push_back(a);
    }
    sort(v.begin(), v.end());
    int last = 1;
    for (int i = 0; i < v.size(); i++) {
        if (last < v[i]) {
            break;
        }
        else {
            last += v[i];
        }
    }
    cout << last;
}

 

PC로 보시는 것을 권장합니다. 

피드백은 언제나 환영입니다. 댓글로 달아주세요 ^-^