문제링크
º https://www.acmicpc.net/problem/2110
사용 알고리즘
º 이분탐색
시간복잡도
º $\mathcal{O}(Nlog(10^{10}))$
풀이
문제에서의 설명이 애매하게 느껴지는데 공유기를 설치한다는 의미는 연속하는 점들을 묶어주는 것과 같은 의미라고 보면 됩니다. 즉, 그룹을 만들어주는 것인데 그룹간의 간격의 최대길이를 지정해 놓고 그 간격으로 최대한의 그룹을 만들어서 묶어주면 그룹이 C개 이상이면 문제를 해결할 수 있습니다.
최대길이를 시작점과 끝점의 거리차로 해서 이분탐색을 시작하여 매 탐색시 그룹간격 최대길이로 그룹을 만들어주는 로직을 해줍니다.
그 로직은 전 점의 좌표와 현 점의 좌표의 거리차를 그룹간격 최대길이를 mid라 할때 mid 이상인지 검사해줍니다. mid미만의 값이면 한 공유기에 넣어도 최대길이를 초과할 일이 없기 같은 공유기에 넣어주고, 아니면 새 그룹으로 시작해줍니다.
따라서 탐색은 최대로 나올 수 있는 좌표 10억과 1의 차이인 $\mathcal{O}(log(10^{10}))$=10
매 탐색시 $\mathcal{O}(N)$의 시간소모. 최종적으로 둘을 곱해줍니다.
소스코드
|
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
|
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int n,c;
vector <long long> v;
cin >> n >> c;
v.resize(n);
for (int i = 0; i < n; i++)
cin >> v[i];
sort(v.begin(), v.end());
int prev,result,ans=0,mid, left = 1, right = v[n - 1]-v[0]; // 오른쪽 최대범위 시작점과 끝점의 거리차
while (left <= right)
{
mid = (left + right) / 2;
result = 1;
prev = v[0];
for (int i = 1; i < n; i++)
{
if (v[i] - prev >= mid) // 현재 설정한 최대거리 이상이면 공유기를 하나더추가해줌
{
result += 1;
prev = v[i];
}
}
if (result >= c) // 공유기 개수가 C이상이면 정답보다 큰지 비교
{
left = mid + 1;
if (mid > ans)
ans = mid;
}
else
right = mid - 1;
}
cout << ans;
return 0;
}
|
cs |
'알고리즘 > BOJ' 카테고리의 다른 글
| 백준 2805번 나무 자르기 (0) | 2020.07.09 |
|---|---|
| 백준 1654번 랜선 자르기 (0) | 2020.07.08 |
| 백준 11651번 좌표 정렬하기 2 (0) | 2020.07.08 |
| 백준 13397번 구간 나누기 2 (0) | 2020.07.08 |
| 백준 1939번 중량제한 (0) | 2020.07.08 |