본문 바로가기
PS/Baekjoon

[백준/C++] 2437번: 저울(G3)

by 이지이즤 2022. 1. 14.
728x90

문제

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

 

2437번: 저울

하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓

www.acmicpc.net

 

 

사용한 알고리즘

 

 

풀이

  1. 각 추의 무게를 오름차순 정렬한다.
  2. 다음 추의 무게가 이전 추까지의 누적(무게)합+1 보다 크면
    측정할 수 없는 무게의 최솟값은 누적합+1 이 된다.

예시)

추의 무게 : 1  1  2  3   6   7  30
누적 합    : 1  2  4  7 13  20  50

이때 무게가 7인 추가 

누적합+1보다 큰 수인 15였다면

14를만들지 못하므로 답은 누적합+1인 14이다. 

 

 

소스코드

#include <iostream>
#include <algorithm>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    // 다음숫자가 누적합+1보다 크면 누적합+1 표현불가

    int n; cin>>n;
    int a[1001];
    for(int i=0; i<n; i++) cin>>a[i];
    // 1. 각 추의 무게를 오름차순 정렬한다.
    sort(a,a+n);
    
    /*
     2. 다음 추의 무게가 이전 추까지의 누적(무게)합+1 보다 크면
        측정할 수 없는 무게의 최솟값은 누적합+1 이 된다. 
    */
    int sum=0;
    for(int i=0; i<n; i++){
        if(a[i]>sum+1){
            cout<<sum+1;
            return 0;
        }
        else sum+=a[i];
    }
    cout<<sum+1;
    return 0;
}
728x90

댓글