코드 복사/붙여넣기 하는 당신이 아름답습니다.

2437 : 저울

풀이

일단 주어진 추들의 무게를 정렬해 보자.

1~w까지의 모든 무게를 만들 수 있다고 가정하자.

1~w를 만들 수 있다면

여기에 무게 k의 추를 추가해서 1~w+k까지의 모든 무게를 만들 수 있다.

하지만 만약 k > w+1이라면 w+을 만들 수 없게 된다.

이제 코드로 옮겨보자.

코드

#include <cstdio>
#include <algorithm>

int n, a[1001];

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }

    std::sort(a, a+n);

    int mx = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] > mx+1) {
            break;
        }
        mx += a[i];
    }

    printf("%d\n", mx+1);

    return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2019-01-23 15:14

Read more posts by this author