BOJ_2110_공유기설치

**백준_공유기 설치 개인 정리글 입니다.

2110번: 공유기 설치

첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가

www.acmicpc.net

아니 딱 절반씩 계속 보면 되는것이 아닌가?

처음에 접근한 것은 저 문장 그대로 코드를 구현하였다. 예상대로 시간초과가 났다. 어떻게 접근해야 할까?

이 문제 접근은 아주 간단하다. 공유기 개수 이다. 처음에 생각한 아이디어는 이분 탐색이었나, 굳이 그럴필요 없다고 생각했다. 왜냐하면 정렬하고 중간값을 계속 찾으면 되기 때문에 C 개수 만큼 ... 그러나 좋은 생각은 아니었다.

정리해보면 실행 흐름은 다음과 같다.

1. 기준길이을 하나 세운다. 기준길이를 기반으로 각 정점 길이 차이( arr[i] 와 arr[i-1] 차이 ) 와 비교한다. 만약 기준길이가 작은 경우 공유기를 설치한다. ????

2. 공유기 개수와 C 를 비교 한다. 공유기 개수가 많으면 간격을 늘린다. 그렇지 않으면 간격을 줄인다. ???

소스코드

+++

참고 :

백준 2110번 공유기 설치 :: 마이구미

이 글은 백준 알고리즘 2110번 "공유기 설치" 를 풀이한다. 풀이 방법으로는 이분(이진) 탐색을 사용한다. 문제 링크 - https://www.acmicpc.net/problem/2110 이분 탐색 - http://mygumi.tistory.com/72 도현이..

mygumi.tistory.com

댓글