-
[BOJ] 2110번 - 공유기 설치Algorithm/BOJ 2022. 6. 20. 23:14
[BOJ] 2110번 - 공유기 설치
https://www.acmicpc.net/problem/2110
2110번: 공유기 설치
첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가
www.acmicpc.net
접근 방식(틀린 풀이)
해당 문제는 풀어본적 있는지 여부에 따라 풀 수 있는지 여부가 달라질 것으로 보인다.
처음에는 공유기를 맨 앞과 맨뒤로 부터 놓은 다음에 하나씩 증가 시키며 Devide 시켜 그 중에 max된 값을 추출하여 값을 구하는 방식으로 구현하였다.
하지만 위와 같은 방식은 O(N^2)이 소요되어 시간 초과가 발생이 된다.
이분 탐색으로 푸는거 같긴 한데 어떤한 부분을 나누어서 접근할지 몰라 다른 사람들의 코드를 참고하였다.
생각지도 못한 부분이 있었는데, 와이파이를 나누는 부분을 이분탐색하여 구현시키는 방법이였다.
알고리즘
와이파이 거리를 기준으로 이분탐색
1. 범위를 나눈다.
2. 범위를 절반으로 나누어 탐색할 공간을 선택한다.
3. 와이파이 갯수가 문제에서 요청한 갯수보다 부족하다면, 거리를 좁혀야 한다.
4. 반대로 범위 안에 안착하게 된다면 해당 범위 내에서 가장 큰 값을 찾아야 한다.
코드
#BOJ 2110번 import sys input = sys.stdin.readline n , target = map(int,input().split()) datas = sorted( [int(input()) for _ in range(n)] ) left , right = 1 , datas[-1] answer = 1 # 신호 떨어지는 값을 이분탐색 while left <= right : gap = (left+right)//2 cnt = 1 before = datas[0] #갯수 세기 for data in datas[1:]: if data-before >= gap : cnt += 1 before = data #갯수는 들어오지만 범위안에 있을 수 있다. if cnt >= target : left = gap+1 answer = gap else : right = gap-1 print(answer)
'Algorithm > BOJ' 카테고리의 다른 글
[BOJ] 20922번 - 겹치는 건 싫어 (0) 2022.06.29 [BOJ] 13144번 - List of Unique Numbers (0) 2022.06.22 [BOJ] 8980번 - 택배 (0) 2022.06.20 [BOJ] 2482번 - 색상환 (0) 2022.06.13 [BOJ] 1700번 - 멀티탭 스케줄링 (0) 2022.06.13