[BOJ 2437] 저울 (C++)

www.acmicpc.net/problem/2437

2437번: 저울

저울 문제

 

구현 방법

이 문제를 해결하기 위해 긴 시간 고민하다가, 도저히 풀이 방법이 떠오르지 않아 검색을 해서 풀이 방법을 검색해본 문제입니다.

 

그리디 문제인 것도 알겠고, 정렬을 해서 어떻게 하면 될 것 같았는데 결국 해답을 찾지 못했습니다.

 

제가 찾은 방법은 다음과 같았습니다.

 

입력받은 원소를 오름차순으로 정렬하고, 첫 번째 원소부터 더해 주는 누적합을 계산합니다.

누적합을 계산해 나가다가 다음 원소가 누적 합보다 크면 (누적합 + 1)을 출력해주고 종료합니다.

 

이 문제의 예제 입력인 3 1 6 2 7 30 1을 예로 들면 1 1 2 3 6 7 30으로 정렬하고, 1부터 누적합을 구해줍니다.

 

누적합이란 다음과 같습니다.

 

• 1 1 2 3 6 7 30      누적합: 1
• 1 1 2 3 6 7 30      누적합: 1+1 = 2
• 1 1 2 3 6 7 30      누적합: 1+1+2 = 4
• 1 1 2 3 6 7 30      누적합: 1+1+2+3 = 7
• 1 1 2 3 6 7 30      누적합: 1+1+2+3+6 = 13
• 1 1 2 3 6 7 30      누적합: 1+1+2+3+6+7 = 20
• 1 1 2 3 6 7 30      누적합: 1+1+2+3+6+7+30 = 50

 

누적합을 구하면서, 다음 원소의 크기가 현재 누적합의 크기보다 크면 멈춥니다.

 

위의 예시중에서는...

 

1 1 2 3 6 7 30       누적합: 20 일 때, 다음 원소인 30이 20보다 크니 멈춥니다.

 

그리고 (현재 누적합+1), 즉 21을 출력해주면 답안입니다.

 

이 풀이 방법을 알고도 이해하는데 엄청 긴 시간이 걸렸습니다.

 

1) 다음 원소가 누적 합보다 크면 멈추는 이유

 

다른 예시를 하나 예로 들어 설명해보겠습니다.

 

누적합이 360인 n개의 수가 있다고 가정합니다. 그럼 n개 숫자로 몇 개의 숫자를 선택해 1~360까지 표현할 수 있습니다.

 

n+1 번째 원소가 200인 경우에, 앞의 n개 숫자로 표현한 1~360에 200을 더하면 201~560까지 표현할 수 있습니다.

 

n+1 번째 원소가 400인 경우, 즉 누적 합보다 큰 경우, n개의 숫자로 표현한 1~360에 400을 더하면 401~760까지 표현할 수 있습니다.

 

즉 누적합 보다 큰 숫자가 오면 360 다음 숫자인 361은 합으로 나타내지 못합니다.

 

위 내용을 아래 소스코드로 구현했습니다.

 

소스코드

#include <bits/stdc++.h>
using namespace std;

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

    int n; cin >> n;
    vector<int> v;

    //추 개수 만큼 입력 받음
    for(int i=0;i<n;i++) {
        int w; cin >> w;
        v.push_back(w);
    }

    //오름차순 정렬
    sort(v.begin(), v.end());

    //무게 누적합
    int weight = 0;

    //시작부터 1이 없으면
    if(v[0] != 1) {
        cout << 1;
        return 0;
    } else {
        //추 개수 만큼 반복하면서, 누적합+1 보다 다음 원소가 크면 break
        for(int i=0;i<n;i++) {
            if(v[i] > weight+1) break;
            
            //누적합 연산
            weight += v[i];
        }
    }

    //break 하기 전 까지의 누적합 + 1 출력
    cout << weight + 1;
}