문제

https://www.acmicpc.net/problem/2110

풀이

프로그래머스에서 풀었던 이분탐색 문제(아직 안올림, 입국심사 문제)와 같이 되는지 확인하는데 n, 되는 값을 찾는데 lg 100000000이 들어서 푸는 문제이다.

다만 저번에는 lower bound, upper bound을 적용하지 않아도 정답이 나와서 의아했는데 똑같이 했는데 여기서 안되는 것을 보면 저번 문제의 테스트 케이스가 이상하지 않았나 싶다.

처음에 틀렸을때는 h[0]을 무조건 가지고 가는 것 때문에 문제가 발생하는 줄 알았는데 곰곰히 생각해보니까 안되는건 없는 것 같다. 만약 안되더라도 양쪽에서 돌리면 되지 않을까 싶다. (반례를 생각해봤는데 없는 듯 함)

실수

• lb, ub 내용을 시간이 된다면 정리해서 체득하자
• 반례를 곰곰히 잘 생각해보자

코드

#define _CRT_SECURE_NO_WARNINGS

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

using namespace std;

vector<int> home;

bool check(int c, int distance) {

	int prev_home = -100000000;
	int temp_c = c;

	for (int i = 0; i < home.size(); i++) {

		if (home[i] - prev_home >= distance) {

			prev_home = home[i];
			c--;

			if (c == 0)
				return true;

		}

	}

	return false;

}

int main() {

	int n, temp, r, l, m, c;

	scanf("%d %d", &n, &c);

	for (int i = 0; i < n; i++) {

		scanf("%d", &temp);
		home.push_back(temp);

	}

	sort(home.begin(), home.end());

	l = 0;
	r = 1000000000;

	while (l < r) {

		m = (r - l) / 2 + l;

		if (check(c, m)) {

			l = m + 1;

		}

		else {

			r = m;

		}

	}

	printf("%d", l - 1);

	return 0;

}