[BAEKJOON] 1477, 13702

※ 소스코드는 각 문제 설명 하단에 <더보기>를 통해 확인하실 수 있습니다.

[gold4, 1477 휴계소 세우기] - 이분탐색

처음엔 우선순위 큐로 접근했으나, 휴계소 사이에 정확히 1개가 아닌 여러개의 휴계소를 설치함으로써 
최대 거리를 좁혀나갈 수 있는 방법이 존재하기 때문에 정확한 답을 도출할 순 없다.

그래서 이분탐색으로 풀어야 한다.
가장 키 포인트는, 구간 사이사이에 휴계소를 설치하는 것인데,
1) 얼만큼의 거리로 휴계소를 지을 것인지, 2) 그 거리 내에서 설치할 수 있는 휴계소의 개수는 몇개인지
두 점을 파악하며 풀이하는 것이 핵심이다.

신경써야 할 예외는, 특정 거리만큼 구간 내에 설치할 때, 등분을 활용하게 되는데,
휴계소가 이미 지어져있는 마지막 구간을 포함하여 등분이 진행되는 경우를 제거해주어야 한다.
간단하게 예를들면, 10과 100에 휴계소가 지어져있고, 그 사이에 10 거리만큼 휴계소를 지은다면, 90/10 = 9개가 지어져야 하는데,
100 위치에는 이미 휴계소가 지어져 있으므로 배제해주어야 한다는 뜻이다.

가장 어렵고 이해가 안된 부분은, 실제 휴계소를 지을 땐, 거리가 일정하지 않을 수 있으므로
일정 거리마다 휴계소를 정확히 M개만 지었을 때를 판별하는 것이 아닌,
휴계소가 M개 이하가 지어지는 모든 경우에, 휴계소를 짓는 거리의 최대값의 최소값을 구해야 하는 것이다.
휴계소가 M개 이하인 모든 경우에 판별하는 이유는, 나머지 휴계소를 구간 사이 어느곳에나 추가해도 현재 최대값은 유지되기 때문이다.

#include <iostream>
#include <queue>
#include <algorithm>
#pragma warning(disable:4996)

using namespace std;

#define MAX 52
int N, M, L, answer = 1000;
int place[MAX];

int main() {
	scanf("%d %d %d", &N, &M, &L);

	place[0] = 0;
	place[N + 1] = L;

	for (int n = 1; n <= N; n++)
		scanf("%d", &place[n]);

	sort(place, place + N + 1);

	int left = 1;
	int right = L - 1;
	while (left <= right) {
		int mid = (left + right) / 2;
		int cnt = 0;
		for (int i = 1; i <= N + 1; i++) {
			int dist = place[i] - place[i - 1];
			int build = dist / mid;
			if (build > 0) {
				cnt += dist % mid == 0 ? build - 1 : build;
			}
		}
		// 더 많이지어졌으면, 거리가 짧은 것이므로
		if (cnt > M) left = mid + 1;
		// 더 적게 지어졌으면, 거리가 긴 것이므로
		else {
			answer = answer < mid ? answer : mid;
			right = mid - 1;
		}
	}

	printf("%d", answer);
}

 

[sliver2, 13702 이상한 술집] - 이분탐색

K명수에 맞춰서 따르려는 막걸리의 양이 동등해야 한다는 점을 기억하고,
막걸리의 최대 값이 2^31-1임에 유념하자.

이분탐색을 통한 막걸리의 값을 mid라 할 때,
N개의 막걸리 주전자에서 mid만큼 따를 때, cnt명에게 동등하게 제공할 수 있는데,

cnt명 수가 K명 수보다 작다면, 막걸리 양이 너무 많은거니까 최대치를 줄이고
cnt명 수가 K명 수보다 크다면, 막걸리 양이 너무 적은거니까 최소치를 키워야하며
cnt명 수가 K명 수와 같을 땐, 동등하게 제공되지만 최대치인지는 알 수 없으므로
이분탐색 조건을 만족할 때까지 최소값을 증가하는 방향으로 설계하는 것이 첫 번째 핵심 포인트이다.

막걸리의 최대 값이 int의 최대범위이므로, mid값을 설정하는 (left+right)/2값이 int 자료형 범위를 초과할 수 있다.
따라서, 관련 left, right, mid, answer에 대해 long long으로 자료형을 설정하는 것이 두 번째 핵심 포인트이다.

#include <iostream>
#pragma warning(disable:4996)

using namespace std;

#define MAX 1000001
#define ll long long

int N, K;
ll answer = 0;
ll kettle[MAX];

int main() {
	scanf("%d %d", &N, &K);
	for (int n = 0; n < N; n++) {
		scanf("%d", &kettle[n]);
	}

	ll left = 1;
	ll right = 2147483647 - 1;
	while (left <= right) {
		ll mid = (left + right) / 2;
		int cnt = 0;
		for (int n = 0; n < N; n++) {
			cnt += kettle[n] / mid;
		}
		if (cnt < K) {
			right = mid - 1;
		}
		else {
			answer = mid;
			left = mid + 1;
		}
	}
	printf("%lld", answer);
}