알고리즘/백준
[BOJ 2437] 저울(C++, 자세한 설명)
I L G N O Y
2020. 7. 11. 16:44
https://www.acmicpc.net/problem/2437
2437번: 저울
하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓�
www.acmicpc.net
해설코드(C++).
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> v;
int val, next = 0, N;
int main() {
cin >> N;
for(int i = 1; i <= N; i++){
cin >> val;
v.push_back(val);
}
sort(v.begin(), v.end());
int next = 1;
for(int i = 0 ;i < v.size(); i++){
if(next < v[i]){
break;
}
next += v[i];
}
cout << next << endl;
return 0;
}
|
next : 측정 가능을 확인해야 하는 값
next < v[i]일 경우, 측정할 수 없는 구간이 생긴다.
for문 내에 next 갱신되기 위한 순간을 생각해보자.
v[i]라는 추가 더해지면, 0 <= (측정 가능 값) < next에서,
v[i] <= (v[i] 추가 측정 가능 값) < v[i] + next가 될 것이다.
v[i]가 만약에 next보다 크다면, 범위에 의해서 측정할 수 없는 구간(next ~ v[i])이 생기게 된다.