YEJIN LEE

“Keep turnin’ the pages”

3 minute read

이분 탐색 Binary Search

문제

오늘도 역시 준성이는 어김없이 색종이와 쿼리를 푸는 데 실패하였다!!

색종이에 열등감을 느낀 준성이는 가위로 눈에 보이는 색종이를 모두 잘라 버리려고 한다!!

색종이를 자를 때는 다음과 같은 규칙을 따른다.

  • 색종이는 직사각형이며, 색종이를 자를 때는 한 변에 평행하게 자른다.
  • 자르기 시작했으면, 경로 상의 모든 색종이를 자를 때까지 멈추지 않는다.
  • 이미 자른 곳을 또 자를 수 없다.
    분노에 찬 가위질을 하던 준성이는 갑자기 하나의 색종이를 정확히 n번의 가위질로 k개의 색종이 조각으로 만들 수 있는지 궁금해졌다.
    궁금하지만 화가 나서 코딩에 집중할 수 없는 준성이 대신 코드를 작성해주도록 하자.

입력

첫째 줄에 현재 휴게소의 개수 N, 더 지으려고 하는 휴게소의 개수 M, 고속도로의 길이 L이 주어진다. 둘째 줄에 현재 휴게소의 위치가 공백을 사이에 두고 주어진다. N = 0인 경우 둘째 줄은 빈 줄이다.

출력

첫째 줄에 M개의 휴게소를 짓고 난 후에 휴게소가 없는 구간의 최댓값의 최솟값을 출력한다.

  • 0 ≤ N ≤ 50
  • 1 ≤ M ≤ 100
  • 100 ≤ L ≤ 1,000
  • 1 ≤ 휴게소의 위치 ≤ L-1
  • N+M < L
  • 모든 휴게소의 위치는 중복되지 않음

  • 입력으로 주어지는 모든 수는 정수

    예제 입력 1 6 7 800 622 411 201 555 755 82

    예제 출력 1 70

🪨풀이

이 문제는 이분탐색과 매개변수탐색을 이용하여 풀 수 있다.

이분탐색은 어떤것을 mid로 하고 범위를 정하고 조건을 결정하는것이 제일 어려운 것 같다. 이게 다 어려우면 이분탐색 자체를 못푸는 것과 마찬가지다. 맞다. 나는 못푼다..,.

fail to bring

이 문제에서 구할 것은 거리이다. 가장 큰 거리의 최솟값을 구해야하므로 휴게소 사이 거리를 구해야할 매개변수로 보고 mid로 놓는다. low와 high는 mid의 범위이므로 고속도로의 거리가 될 것이다.

고속도로 사이사이에 휴게소를 mid의 거리를 두고 설치해볼 것인데, 여기서 이미 설치된 휴게소가 있으므로 이미 설치된 휴게소 사이사이에 새로운 휴게소를 설치하게 된다.

이미 설치된 휴게소 사이 거리를 mid로 나누어 그 사이에 몇 개의 휴게소가 들어갈 수 있는지 구하고, 그 값들을 모두 합하여 총 몇 개의 휴게소가 새로 들어갈 수 있는지 구한다.
만약 이 개수가 M과 같으면 그만큼 설치하면 되는 것이고, M보다 작아서 더 설치해야하는 경우이면 거리를 좁혀야하므로 high = mid-1로 mid의 값을 줄이고, 반대로 설치를 줄여야한다면 low = mid+1로 mid 거리를 늘리면서 탐색한다.

이미 설치된 휴게소임을 판별하는 방법은 dist/mid로 나누어 그 사이에 휴게소가 몇 개 들어가는지 셀 때, 나머지가 0으로 나누어 떨어지면 mid거리로 휴게소를 세울 때 마지막이 이미 있는 휴게소와 겹친다는 뜻이므로 count–를 해준다.

💻코드

/*
* [백준 1477] 휴게소 세우기
* 다솜이는 유료 고속도로를 가지고 있다. 다솜이는 현재 고속도로에 휴게소를 N개 가지고 있는데, 휴게소의 위치는 고속도로의 시작으로부터 얼만큼 떨어져 있는지로 주어진다. 다솜이는 지금 휴게소를 M개 더 세우려고 한다.

* 다솜이는 이미 휴게소가 있는 곳에 휴게소를 또 세울 수 없고, 고속도로의 끝에도 휴게소를 세울 수 없다. 휴게소는 정수 위치에만 세울 수 있다.

* 다솜이는 이 고속도로를 이용할 때, 모든 휴게소를 방문한다. 다솜이는 휴게소를 M개 더 지어서 휴게소가 없는 구간의 길이의 최댓값을 최소로 하려고 한다. (반드시 M개를 모두 지어야 한다.)

* 예를 들어, 고속도로의 길이가 1000이고, 현재 휴게소가 {200, 701, 800}에 있고, 휴게소를 1개 더 세우려고 한다고 해보자.

* 일단, 지금 이 고속도로를 타고 달릴 때, 휴게소가 없는 구간의 최댓값은 200~701구간인 501이다. 하지만, 새로운 휴게소를 451구간에 짓게 되면, 최대가 251이 되어서 최소가 된다.
*
* [알고리즘]
* 이분 탐색/ 매개 변수 탐색
*/

#include<iostream>
#include<algorithm>
#include<vector>	

using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, M, L;			// 휴게소 개수, 더 지으려는 휴게소 개수, 고속도로 길이
	vector<int> locations;	// 휴게소 위치

	cin >> N >> M >> L;
	locations.push_back(0);
	locations.push_back(L);
	for (int i = 0; i < N; i++) {
		int tmp; cin >> tmp;
		locations.push_back(tmp);
	}
	sort(locations.begin(), locations.end());

	int low = 0; int high = L;
	int mid, res = 0;
	while (low <= high) {
		mid = (low + high) / 2;
		
		int count = 0;
		for (int i = 1; i < locations.size(); i++) {
			int dist = locations[i] - locations[i - 1];
			count += (dist / mid);
			if (dist % mid == 0) count--;
		}
		if (count > M) low = mid + 1;
		else {
			high = mid - 1;
			res = mid;
		}
	}
	cout << res;

	return 0;

}

You may also enjoy