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

문제 링크: www.acmicpc.net/problem/2437

2437번: 저울

1) 주의할 점

- 브루트포스 -> 2^1000 -> TLE발생

- DP -> 방법이 떠오르지 않는다

 

2) 구현

- 도저히 방법이 떠오르지 않아 질문게시판에서 힌트를 얻어서 해결했다

- 우선 Result = 1로 설정을 한다(양의 정수 중 가장 낮은 값이므로). 이때, Result는 지금까지 원소들의 합 + 1이라고 생각하면 된다

- 입력받은 모든 수를 Arr[]배열에 저장한 후, 오름차순으로 정렬한다

- 0~Num-1번까지의 정렬된 수를 Result와 비교한다

- Result < Arr[i]인 경우와 나머지의 경우를 비교한다. 이때, Result와 비교하는 이유는, Result-1까지는 원소들의 합으로 표현이 가능하니 Result는 가능한가?라고 생각하면 된다.

- Result < Arr[i]인 경우, Result수를 표현할 수 없으므로 Result를 출력한다. 이외의 경우엔 Result+=Arr[i]를 수행하고 다음 원소와 비교한다

- 이때, 위의 조건에서 2가지 의문이 들 수 있다

- 첫째, 원소 N개로 [0,Result-1] 표현이 가능 + Arr[n+1]<=Result인 경우 -> [0,Result-1 + Arr[n+1]] 표현 가능?

→ [0,Result-1] + [0+Arr[n+1],Result-1+Arr[n+1]] = [0,Result-1 + Arr[n+1]]가 성립하기 때문에 가능하다

- 둘째, Arr[i-1]<=Arr[i]<=Result를 만족하는 원소들을 N까지 더해서 Result의 값을 갱신했을 뿐인데, 0~Result-1까지 모든 수가 표현이 어떻게 가능한가?

→직접 몇가지의 경우를 생각해서 해본다면 가능하다는 것을 알 수 있다. 특수조건인 Arr[i-1]<=Arr[i]<=Result 한정에서만 가능하다 (증명방법은 명확하게 안떠올라서 보류..)

 

#include <iostream>
#include <algorithm>
using namespace std;
int arr[1000];
int num,result=1;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> num;
    for(int i=0;i<num;i++)
        cin>>arr[i];
    sort(arr,arr+num);
    for(int i=0;i<num;i++){
        if(result<arr[i]){
            break;
        }
        result+=arr[i];
    }
    cout<<result;
    return 0;
}