[C언어/C++] 2437번 저울 풀이 + 반례 모음

https://www.acmicpc.net/problem/2437

2437번: 저울

간결한 그리디 문제입니다.

 

저울 문제를 풀 경우 코드포스의 이 문제도 1분컷으로 쉽게 풀 수 있습니다.

https://codeforces.com/contest/1660/problem/A

괜찮은 예제에 대한 설명을 읽으시면 바로 이해가 갈 거라고 예상합니다.

1, 2, 4, 8, 16의 추를 가진 경우입니다.

 

1 - 가능 ( 1 )

2 - 가능 ( 2 )

3 - 가능 ( 2 + 1 )

4 - 가능 ( 4 )

5 - 가능 ( 4 + 1 )

6 - 가능 ( 4 + 2 )

7 - 가능 ( 4 + 2 + 1 )

8 - 가능 ( 8 )

.

.

32 - 불가능 (다 더해도 31입니다.)

 

위의 예시에서 32는 앞의 숫자를 모두 더해도 만들 수 없는 수였기 때문에 만드는 것이 불가능했습니다.

여태까지 모든 추 무게의 합 + 1보다 큰 값이 다음 추의 무게로 왔을 때는 그다음 추의 값을 측정할 수 없습니다.

위의 경우, 정답은 (이전까지의 모든 추의 무게 + 1)입니다.

위의 경우가 없을 시, 정답은 (모든 추의 무게의 합 + 1)입니다.

 

반례랑 제 코드 알려드리겠습니다.

 

5
1 2 4 8 16

answer : 32


900
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 

answer : 901

1
1

answer : 2

1
2

answer : 1

 

#include <stdio.h>
#include <algorithm>
int main() {
    int sum = 0, n;scanf("%d", &n);
    int arr[1000] = {};
    for(int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    std::sort(arr, arr+n); //정렬은 필수입니다.
    for(int i = 0; i < n; i++) {
        if(arr[i] <= sum +1) sum +=arr[i];
        else break;
    }
    printf("%d", sum+1);
}