반응형
https://www.acmicpc.net/problem/20917
20917번: 사회적 거리 두기
Albert는 L대학에서 주최하는 Hackathon 행사 진행을 도와주기로 했는데, 사회적 거리 두기 방침에 따라 모든 참가자들을 최대한 멀리 떨어트려 좌석 배정을 해주려 한다. 이를 위해 아주 길다란 복
www.acmicpc.net
[ 문제풀이 ]
1. n과 s를 입력받고, vector<int> arr에 콘센트 좌표를 저장합니다.
2. arr를 오름차순으로 정렬하고, a = 0, b = 1,000,000,000으로 저장한 후 매개변수 탐색을 실시합니다.
3. m = (a + b) / 2를 통해 m을 갱신하고, tmp = arr[ 0 ], cnt = 1로 시작하여 이분 탐색을 이용해 다음 콘센트의 위치를 찾습니다. < lower_bound(arr.begin(), arr.end(), tmp + m) >
4. 다음 콘센트의 위치가 범위를 벗어나지 않으면 cnt++를 해주고, cnt의 값이 s보다 크거나 같으면 true를 반환하고, 그렇지 않다면 false를 반환합니다.
5. true를 반환받으면 ans = m 후 a = m + 1로 갱신해 주고, false를 반환받으면 b = m으로 갱신해 주고 매개변수탐색을 계속 진행합니다.
6. a < b일 때까지 계속 반복해 준 후 ans를 출력해 줍니다.
[ 소스코드 ]
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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 | #include<iostream> #include<algorithm> #include<vector> using namespace std; int T; int n, s; vector<int> arr; bool check(int m) { int tmp = arr[0]; int cnt = 1; while (1) { auto it = lower_bound(arr.begin(), arr.end(), tmp + m); if (it == arr.end()) break; tmp = *it; cnt++; } if (cnt >= s) return true; return false; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> T; while (T--) { cin >> n >> s; arr.clear(); for (int i = 0; i < n; i++) { int num; cin >> num; arr.push_back(num); } sort(arr.begin(), arr.end()); int a, b; a = 0; b = 1000000000; int ans = 0; while (a < b) { int m = (a + b) / 2; if (check(m)) { ans = m; a = m + 1; } else { b = m; } } cout << ans << '\n'; } } | cs |
반응형
'백준' 카테고리의 다른 글
| [ 백준 ] 11311번 - Jug Hard (C++) (0) | 2023.10.26 |
|---|---|
| [ 백준 ] 14881번 - 물통 문제 (C++) (0) | 2023.10.25 |
| [ 백준 ] 1132번 - 합 (C++) (0) | 2023.10.23 |
| [ 백준 ] 4395번 - Steps (C++) (0) | 2023.10.22 |
| [ 백준 ] 17433번 - 신비로운 수 (C++) (0) | 2023.10.21 |