티스토리 뷰
728x90
C++ 이분탐색
지금까지 풀었던 이분탐색 문제랑 비슷한 문젠데 난이도가 조금 높은건 기준정하는 함수에 필요한 계산이 좀 많아서 때문인 것 같다.
접근방법
간격을 1부터 가장 좌표값이 큰 값을 범위로 이분탐색한다.
집 좌표값 배열은 정렬해둔다.
간격이 mid일때 공유기를 설치할 수 있는 개수가 C개 이상이면 더 큰 간격에서 이분탐색
C개 미만이면 더 좁은 간격에서 이분탐색
소스코드
#include <iostream>
#include <algorithm>
using namespace std;
int N,C;
int houses[200000];
bool isEnough(long long d){
int total = 0;
int a = houses[0];
for(int i = 1 ; i < N ; i++){
if(a+d <= houses[i]){
total++;
a = houses[i];
}
}
return total+1>=C ? true : false;
}
long long binarySearchMax(long long s, long long e){
long long mid = 0;
while(s <= e){
mid = (s+e)/2;
if(isEnough(mid)){
s = mid+1;
}else{
e = mid-1;
}
}
return s-1;
}
int main(){
cin >> N >> C;
for(int i = 0 ; i < N ; i++){
cin >> houses[i];
}
sort(houses, houses+N);
cout << binarySearchMax(1, houses[N-1]);
return 0;
}
728x90
'알고리즘 문제풀이' 카테고리의 다른 글
[백준 1764] 알고리즘 60일차 : 듣보잡 (0) | 2021.01.07 |
---|---|
[백준 10815] 알고리즘 59일차 : 숫자 카드 (0) | 2021.01.06 |
[백준 1934]알고리즘 57일차 : 최소공배수 (0) | 2021.01.04 |
[백준 2805] 알고리즘 56일차 : 나무 자르기 (0) | 2020.12.30 |
[백준 1654]알고리즘 55일차 : 랜선 자르기 (0) | 2020.12.29 |
250x250
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- 문자열
- 웹크롤링
- 이분탐색
- 스택
- 정렬
- 토마토
- 최단경로
- 자바
- Stack
- 동적계획법
- 파이썬
- 트리
- Swift
- c++
- 투포인터
- 그리디알고리즘
- 브루트포스
- 백준
- 프로그래머스
- dfs
- 최소힙
- 알고리즘
- BFS
- 최대힙
- dp
- 우선순위큐
- 수학
- 백트래킹
- 게임이론
- 다이나믹프로그래밍
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
글 보관함