Algorithm ๐ง๐ป๐ป/๋ฐฑ์ค(BOJ)
[๋ฐฑ์ค,c++] 2141๋ฒ - ์ฐ์ฒด๊ตญ
dkswnkk
2022. 9. 13. 18:16
๋ฌธ์
2141๋ฒ: ์ฐ์ฒด๊ตญ
์ฒซ์งธ ์ค์ N(1 ≤ N ≤ 100,000)์ด ์ฃผ์ด์ง๋ค. ๋ค์ N๊ฐ์ ์ค์๋ X[1], A[1], X[2], A[2], …, X[N], A[N]์ด ์ฃผ์ด์ง๋ค. ๋ฒ์๋ |X[i]| ≤ 1,000,000,000, 0 ≤ A[i] ≤ 1,000,000,000 ์ด๋ฉฐ ๋ชจ๋ ์ ๋ ฅ์ ์ ์์ด๋ค.
www.acmicpc.net
์ฝ๋
#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long int
using namespace std;
ll sum[100001];
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
ll N; cin>>N;
vector<pair<ll, ll>> v;
for(int i=0; i<N; i++){
ll a, b; cin>>a>>b;
v.push_back({a, b});
}
sort(v.begin(), v.end());
sum[0] = v[0].second;
for(int i=1; i<N; i++) sum[i] = sum[i-1] + v[i].second; // ์ฌ๋ ์ ๋์ ํฉ
ll start = 0, end = N-1;
ll idx = 1e9;
while(start <= end){
ll mid = (start + end) / 2;
if(sum[mid] >= sum[N-1] - sum[mid]){
end = mid - 1;
idx = min(idx, v[mid].first);
}
else start = mid + 1;
}
cout<<idx;
}
ํ์ด
๋ฌธ์ ๋ถ๋ฅ๋ ๊ทธ๋ฆฌ๋๋ก ๋์ด์๋๋ฐ ์ ๋ ๋์ ํฉ๊ณผ ์ด๋ถ ํ์์ ์ด์ฉํ์ฌ ํ์์ต๋๋ค.
- ๊ฐ ์์น๊น์ง์ ์ฌ๋ ์๋ฅผ ๋์ ํฉ์ ํตํด ๊ฐฑ์ ํฉ๋๋ค.
- ์ด๋ถํ์์ ํตํด ์ฐ์ฒด๊ตญ์ ์ธ์ธ ์์น๋ฅผ ์ ํฉ๋๋ค.
- ํ์ฌ ์์น ๊น์ง ๋ํ ์ฌ๋ ์๊ฐ ์ฐ์ธก์ ์ฌ๋๋ค ์ ๋ณด๋ค ํฌ๋ค๋ฉด ํ ์นธ ๋ ์ข์ธก์ผ๋ก ๊ฐ๋ ๊ฒ์ด ์ ๋ฆฌํฉ๋๋ค.
- ํ์ฌ ์์น๊น์ง ๋ํ ์ฌ๋ ์๋ณด๋ค ์ฐ์ธก์ ์ฌ๋๋ค ์๊ฐ ๋ ํฌ๋ค๋ฉด ์ฐ์ธก์ผ๋ก ํ ์นธ ๋ ๊ฐ๋ ๊ฒ์ด ์ ๋ฆฌํฉ๋๋ค.
- ์ด๋ฅผ ํตํด ์ต์ ์ ์์น๋ฅผ ์ฐพ์ต๋๋ค.