[Algorithm]Baekjoon 2437번 : 저울

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

2437번: 저울

 
int n;
int weights[1001];
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> n;
 
    for (int i = 0; i < n; ++i)
    {
        cin >> weights[i];
    }
 
    sort(weights, weights + n);
 
    int end = 1;
 
    for (int i = 0; i < n; ++i)
    {
        if (weights[i] > end) break;
 
        end += weights[i];
    }
    
    cout << end;
    
}
 

 

아무리 생각해도 방법이 떠오르지 않아 다른사람 풀이를 봤다.

 

이분 설명이 제일 좋다.

https://aerocode.net/392

백준 2437 풀이 및 해설

 

결과적인것만 보면, 선이 끊어지는 순간이 만들 수 없는 값이므로 그 지점을 찾아야하는 것 같다.

매 반복마다 선의 끝부분이 새로 시작해야하는 지점보다 크면 연결이 되는거니 그대로 값을 누적시키고, 작아지는순간 끊어지는 것이다. (선의 연결여부를 구하는걸 생각해보면 된다)