https://www.acmicpc.net/problem/1654
๋ฌธ์
์ง์์ ์๊ฐ์ ๋ณด๋ด๋ ์ค์์์ ๋ฐ์ฑ์์ ๋ถ๋ฆ์ ๋ฐ๊ณ ๊ธํ ๋ฌ๋ ค์๋ค. ๋ฐ์ฑ์์ด ์บ ํ ๋ ์ธ N๊ฐ์ ๋์ ์ ๋ง๋ค์ด์ผ ํ๋๋ฐ ๋๋ฌด ๋ฐ๋น ์ ์์์ด์๊ฒ ๋์์ ์ฒญํ๋ค.
์ด๋ฏธ ์ค์์์ ์์ฒด์ ์ผ๋ก K๊ฐ์ ๋์ ์ ๊ฐ์ง๊ณ ์๋ค. ๊ทธ๋ฌ๋ K๊ฐ์ ๋์ ์ ๊ธธ์ด๊ฐ ์ ๊ฐ๊ฐ์ด๋ค. ๋ฐ์ฑ์์ ๋์ ์ ๋ชจ๋ N๊ฐ์ ๊ฐ์ ๊ธธ์ด์ ๋์ ์ผ๋ก ๋ง๋ค๊ณ ์ถ์๊ธฐ ๋๋ฌธ์ K๊ฐ์ ๋์ ์ ์๋ผ์ ๋ง๋ค์ด์ผ ํ๋ค. ์๋ฅผ ๋ค์ด 300cm ์ง๋ฆฌ ๋์ ์์ 140cm ์ง๋ฆฌ ๋์ ์ ๋ ๊ฐ ์๋ผ๋ด๋ฉด 20cm๋ ๋ฒ๋ ค์ผ ํ๋ค. (์ด๋ฏธ ์๋ฅธ ๋์ ์ ๋ถ์ผ ์ ์๋ค.)
ํธ์๋ฅผ ์ํด ๋์ ์ ์๋ฅด๊ฑฐ๋ ๋ง๋ค ๋ ์์ค๋๋ ๊ธธ์ด๋ ์๋ค๊ณ ๊ฐ์ ํ๋ฉฐ, ๊ธฐ์กด์ K๊ฐ์ ๋์ ์ผ๋ก N๊ฐ์ ๋์ ์ ๋ง๋ค ์ ์๋ ๊ฒฝ์ฐ๋ ์๋ค๊ณ ๊ฐ์ ํ์. ๊ทธ๋ฆฌ๊ณ ์๋ฅผ ๋๋ ํญ์ ์ผํฐ๋ฏธํฐ ๋จ์๋ก ์ ์๊ธธ์ด๋งํผ ์๋ฅธ๋ค๊ณ ๊ฐ์ ํ์. N๊ฐ๋ณด๋ค ๋ง์ด ๋ง๋๋ ๊ฒ๋ N๊ฐ๋ฅผ ๋ง๋๋ ๊ฒ์ ํฌํจ๋๋ค. ์ด๋ ๋ง๋ค ์ ์๋ ์ต๋ ๋์ ์ ๊ธธ์ด๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
์ ๋ ฅ
์ฒซ์งธ ์ค์๋ ์ค์์์ด ์ด๋ฏธ ๊ฐ์ง๊ณ ์๋ ๋์ ์ ๊ฐ์ K, ๊ทธ๋ฆฌ๊ณ ํ์ํ ๋์ ์ ๊ฐ์ N์ด ์ ๋ ฅ๋๋ค. K๋ 1์ด์ 10,000์ดํ์ ์ ์์ด๊ณ , N์ 1์ด์ 1,000,000์ดํ์ ์ ์์ด๋ค. ๊ทธ๋ฆฌ๊ณ ํญ์ K โฆ N ์ด๋ค. ๊ทธ ํ K์ค์ ๊ฑธ์ณ ์ด๋ฏธ ๊ฐ์ง๊ณ ์๋ ๊ฐ ๋์ ์ ๊ธธ์ด๊ฐ ์ผํฐ๋ฏธํฐ ๋จ์์ ์ ์๋ก ์ ๋ ฅ๋๋ค. ๋์ ์ ๊ธธ์ด๋ 231-1๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์์ฐ์์ด๋ค.
์ถ๋ ฅ
์ฒซ์งธ ์ค์ N๊ฐ๋ฅผ ๋ง๋ค ์ ์๋ ๋์ ์ ์ต๋ ๊ธธ์ด๋ฅผ ์ผํฐ๋ฏธํฐ ๋จ์์ ์ ์๋ก ์ถ๋ ฅํ๋ค.
ํ์ด
lan ํจ์๋ length ๊ธธ์ด์ ๋์ ์ด ๋์ค๋ ๊ฐฏ์๋ฅผ ๋ฐํํ๋ค.
lan() ๊ฐ์ด n๋ณด๋ค ํฌ๊ฑฐ๋ ๊ฐ๊ฒ ๋์ค๋ length๋ค์ ์ต๋๊ฐ์ ๊ตฌํ๋ฉด๋จ.
์ฆ length์ ๋ง ๋์ ํด์ ์กฐ๊ฑด์ ๋ง๋๊ฑธ ๊ณจ๋ผ๋ด๋ฉด ๋๋๋ฐ,
์ด ๊ณผ์ ์์ ์๊ฐ์ด๊ณผ๊ฐ ๋๊ธฐ ๋๋ฌธ์ ์ด๋ถํ์์ ์ฌ์ฉํ๋ค
length ๊ธธ์ด๊ฐ์ ๋ํ์ฌ ํด๋น ๊ธธ์ด์ ๋์ค๋ ๋์ ๊ฐฏ์๊ฐ n๋ณด๋ค ์์ผ๋ฉด ๊ธธ์ด๋ฅผ ๋๋ฆฌ๊ณ , ํฌ๋ฉด ๊ธธ์ด๋ฅผ ์ค์ด๋ ๋ฐฉ์์ผ๋ก ์ด๋ถํ์์ ์งํํ๋ค.
์ด๋ถํ์์ ์ด๋ป๊ฒ ๊ตฌํํ๋์ ๋ฐ๋ผ ๊ทธ ๋ํ ์ผ์ ๋ฐ๋ผ ๋ฐ๋ก๊ฐ ์๊ธฐ๋ ์ ์ํ๋ฆฐ๋ค๋ฉด ์๋ ๊ธ์ ์ฐธ๊ณ ํ์ (๋ฐ๋ก๋ฅผ ์ ๋ง ์ ์ ๋ฆฌํด์คฌ๋ค)
๋ง์ฝ 47%์์ ํ๋ ธ์ต๋๋ค ๋๋ 49%์์ ํ๋ ธ์ต๋๋ค ๊ฐ ๋ฌ๋ค๋ฉด
์ด๋ถํ์์ ์ฌ์ฉํ๋ ๋ณ์๋ค( start, end, mid )๊ณผ ๋ต์ ํด๋นํ๋ ๋ณ์์ ๋ฒ์๋ฅผ ํ์ธํ์
๋์ ๊ธธ์ด์ ๋ฒ์๊ฐ ๋งค์ฐ ํฌ๊ธฐ ๋๋ฌธ์ ๋์ ์ ๊ธธ์ด์ ๋์ํ๋ ๋ณ์๋ค(์์ ๋งํ ์ด๋ถํ์์ ์ฌ์ฉํ๋ ๋ณ์๋ค๊ณผ ๋ต ๋ณ์)์ int๋ณด๋ค ํฐ ๋ฒ์์ธ long long์ผ๋ก ๋ฐ๋ก ์ง์ ์ด ํ์ํ๋ค
// ํ์ด : https://whkakrkr.tistory.com
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int k, n;
int lan(vector<int>&v, int length) {
int cnt=0;
for(int i=0; i<k; i++) {
cnt += v[i]/length;
}
return cnt;
}
int main() {
cin >> k >> n;
vector<int> v(k);
for(int i=0; i<k; i++) {
cin >> v[i];
}
long long ans=1;
long long start=1, end=*max_element(v.begin(), v.end());
while(start<=end) {
long long mid = (start+end)/2;
int tmp = lan(v, mid);
if(tmp < n) {
end = mid-1;
} else {
ans = max(mid, ans);
start = mid+1;
}
}
cout << ans;
}
'๐๏ธ ICPC Sinchon > Binary Search' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[BOJ][C++] ๋ฐฑ์ค 1365๋ฒ: ๊ผฌ์ธ ์ ๊น์ค (0) | 2024.09.30 |
---|---|
[BOJ][C++] ๋ฐฑ์ค 2805๋ฒ: ๋๋ฌด ์๋ฅด๊ธฐ (0) | 2023.11.06 |
[BOJ][C++] ๋ฐฑ์ค 1107๋ฒ: ๋ฆฌ๋ชจ์ปจ (0) | 2023.01.21 |
[BOJ] ๋ฐฑ์ค 2110๋ฒ: ๊ณต์ ๊ธฐ ์ค์น (0) | 2022.10.13 |
[BOJ] ๋ฐฑ์ค 10816๋ฒ: ์ซ์ ์นด๋ 2 (0) | 2022.10.13 |