์ผ | ์ | ํ | ์ | ๋ชฉ | ๊ธ | ํ |
---|---|---|---|---|---|---|
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 |
28 | 29 | 30 | 31 |
- IntelliJ
- SSAFY 11๊ธฐ
- react
- ์คํ๋ง
- viroreact
- SSAFYcial
- ์คํ๋ง๋ถํธ
- connetion refused
- viro
- Spring
- ์ธํผ์
- Lombok
- ์ธํผ12๊ธฐ
- maven
- ๋ฆฌ์กํธ
- ์ธํผ
- ssafy 12๊ธฐ
- boj
- ๋ถ์ธ๊ฒฝ์บ ํผ์ค
- Security
- viro-community
- arduino uno wifi rev2
- springboot
- ssafy job fair
- ์๊ณ ๋ฆฌ์ฆ
- SSAFY
- ๋ฐฑ์ค
- React Native CLI
- MySQL
- ํ์๊ฐ์
- Today
- Total
log
[BOJ 2110] ๊ณต์ ๊ธฐ ์ค์น ๋ณธ๋ฌธ
๐ ๋ฌธ์
https://www.acmicpc.net/problem/2110
๐ป ์ฝ๋
#include <iostream>
#include <algorithm>
using namespace std;
int N, M;
int arr[200001];
int main() {
cin >> N >> M;
for (int i = 0; i < N; i++) cin >> arr[i];
sort(arr, arr + N);
int start = 1;
int end = arr[N - 1] - arr[0];
int mid = 0;
int result = 0;
while (start <= end) {
mid = (start + end) / 2;
int cnt = 1; // ๋ฐฐ์น๋ ๊ณต์ ๊ธฐ ๊ฐ์
int temp = 0;
for (int i = 1; i < N; i++) {
int len = arr[i] - arr[temp];
if (len >= mid) {
cnt++;
temp = i;
}
}
if (cnt < M) end = mid - 1;
else {
result = mid;
start = mid + 1;
}
}
cout << result << '\n';
}
๋ฉ๋ชจ๋ฆฌ ๋ฐ ์๊ฐ
๐ก ํ์ด
๊ฐ์ฅ ์ธ์ ํ ๋ ๊ณต์ ๊ธฐ ์ฌ์ด์ ์ต๋ ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ๋ ๋ฌธ์ ์ด๊ธฐ ๋๋ฌธ์ ์ ์ผ ์ฒซ๋ฒ์งธ ์ง์๋ ๋ฌด์กฐ๊ฑด ๊ณต์ ๊ธฐ๋ฅผ ์ค์นํ ๊ฒ → ์ต๋ ๊ฑฐ๋ฆฌ๊ฐ ๋์ฌ ์ ์์
int cnt = 1; // ๋ฐฐ์น๋ ๊ณต์ ๊ธฐ ๊ฐ์
int temp = 0;
for (int i = 1; i < N; i++) {
int len = arr[i] - arr[temp];
if (len >= mid) {
cnt++;
temp = i;
}
}
temp๋ ๋ง์ง๋ง์ผ๋ก ๊ณต์ ๊ธฐ๊ฐ ์ค์น๋ ์ขํ๊ฐ ์ ์ฅ๋ ์ธ๋ฑ์ค
- ๋ง์ง๋ง์ผ๋ก ์ค์น๋ ๊ณต์ ๊ธฐ ์์น์ ํ์ฌ ์ง์ ์ขํ๋ฅผ ๋น๊ตํ์ฌ mid, ์ฆ ์ต๋๊ฑฐ๋ฆฌ๋ก ๊ฐ์ ํ ๊ฑฐ๋ฆฌ๋ณด๋ค ํฌ๊ฑฐ๋ ๊ฐ์ผ๋ฉด ํด๋น ์ง์ ์ขํ์ ๊ณต์ ๊ธฐ ์ค์น๊ฐ ๊ฐ๋ฅ
- ๊ณต์ ๊ธฐ ์ค์น ํ temp ๊ฐ์ ๋ง์ง๋ง์ผ๋ก ์ค์น๋ ๊ณต์ ๊ธฐ ์ขํ(i)๋ก ๊ฐฑ์ ๋ฐ ์ค์น๋ ๊ณต์ ๊ธฐ ๊ฐ์(cnt)๋ฅผ ์ฆ๊ฐ
if (cnt < M) end = mid - 1;
else {
result = mid;
start = mid + 1;
}
- ์ค์นํ๊ณ ์ ํ๋ ๊ณต์ ๊ธฐ ๊ฐ์(M)๋ณด๋ค ํ์ฌ ์ต๋ ๊ฑฐ๋ฆฌ๋ก ๊ฐ์ ํ ๊ฐ(mid)์์ ์ค์น๋ ๊ณต์ ๊ธฐ ๊ฐ์(cnt)๊ฐ ๋ ์์ผ๋ฉด ๊ฑฐ๋ฆฌ๋ฅผ ์ค์ธ๋ค
- cnt๊ฐ ๋ ํฌ๋ฉด result๋ฅผ ๊ฐฑ์ ํ๊ณ ๊ฑฐ๋ฆฌ๋ฅผ ๋ ๋๋ฆฐ ํ ๋ค์ ๊ณ์ฐํ๋ค
'Algorithm > Baekjoon' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[BOJ 1863] ์ค์นด์ด๋ผ์ธ ์ฌ์ด๊ฑฐ (1) | 2024.04.07 |
---|---|
[BOJ 22871] ์ง๊ฒ๋ค๋ฆฌ ๊ฑด๋๊ธฐ (large) (0) | 2024.03.17 |