일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- react
- HTML
- js
- 장고
- Git
- 파이썬 알고리즘
- django ORM
- API
- 알고리즘 연습
- Baekjoon
- es6
- django rest framework
- MAC
- Django
- 알고리즘 풀이
- form
- AWS
- CSS
- javascript
- DRF
- 알고리즘
- django widget
- 파이썬
- 알고리즘 문제
- java
- c++
- web
- Algorithm
- 백준
- PYTHON
Archives
- Today
- Total
수학과의 좌충우돌 프로그래밍
[C++] BAEKJOON 2110 공유기 설치 본문
https://www.acmicpc.net/problem/2110
이분탐색
을 활용하여 해결하였습니다.
가장 인접한 두 공유기 사이의 최대 거리 를 구하는 문제입니다. 이 거리를 answer 라고 하면 answer 값을 구해주기 위해서 이분탐색으로 찾아갑니다. 최소값은 1 이므로 left 는 1로 초기화하고, 최대값은 양 쪽 끝의 공유기 거리 이므로 right 는 이 값으로 초기화 해줍니다. 가장 인접한 두 공유기 사이의 거리를 mid 로 결정하였을 때는 놓을 수 있는 공유기의 개수, count 를 계산해줍니다. count 를 확인하기 위해서는 마지막에 공유기를 설치한 집부터의 거리가 mid 보다 크면 공유기를 설치하고 개수를 증가해줍니다. 놓을 수 있는 공유기의 개수 count 가 놓아야하는 공유기의 개수 C 보다 크다면 mid 를 증가시키고 그렇지 않으면 mid 를 감소시켜면서 answer를 찾게 됩니다.
#include <iostream>
#include <algorithm>
using namespace std;
int home[200000];
int main(){
int N,C;
cin >> N >> C;
for (int i=0;i<N;i++){
cin >> home[i];
}
sort(home, home+N);
int answer = 0;
long long left = 1;
// 두 공유기 사이의 최대 거리는 맨 뒤와 맨 앞의 차이
long long right= home[N-1]-home[0];
while (left<=right){
long long mid = (left+right)/2;
int count=1;
int start = home[0];
for (int i=1;i<N;i++){
int distance = home[i] - start;
if (distance >= mid){
count++;
start = home[i];
}
}
if (count>=C){
left = mid+1;
answer = mid;
}
else {
right = mid-1;
}
}
cout << answer << "\n";
}
'알고리즘 > C++' 카테고리의 다른 글
[C++] BAEKJOON 2606 바이러스 (0) | 2019.09.22 |
---|---|
[C++] BAEKJOON 1717 집합의 표현 (0) | 2019.09.22 |
[C++] BAEKJOON 2805 나무 자르기 (0) | 2019.09.21 |
[C++] BAEKJOON 1654 랜선 자르기 (0) | 2019.09.21 |
[C++] BAEKJOON 1074 Z (0) | 2019.09.20 |
Comments