1477번 휴게소 세우기

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

 

 

1. 휴게소의 위치는 1이 아니라 0부터 시작한다.

"길이가 1,000"이라는 말과 "~휴게소가 없는 구간의 최댓값은 200~701구간인 501이다.~"

이라는 말 그리고 최대 길이가 1000이라는 조건이 존재할 때, 시작 위치가 0이라는 뜻이다.

 

2. 처음에는 chk() 함수의 return을 int로 했었다.(0, 1, 2)

0 : cnt > M

1 : cnt == M

2 : cnt < M

 

[최초 구현 로직]

1과 2 일 때, right = mid - 1; → "1"일 때만, ret = min(ret, mid); 수행

0일 때, left = mid + 1;

 

하지만, cnt == M일 때만 최솟값을 갱신할 필요가 없었다.

 

이유는 cnt < M 즉, 휴게소 사이의 거리의 최댓값이 mid라고 할 때, 

휴게소 사이의 간격이 mid인 경우에 계산한 것이 cnt(<M)이므로,

새롭게 설치한 휴게소들 사이 사이에 추가적으로 더 휴게소를 설치해도 mid보다 짧기 때문에 상관없다.

mid는 최댓값이다. 그 사이에 휴게소가 더 설치되어도 mid는 변함이 없다. M - cnt만큼 설치하면 된다.

 

3. 시작 위치인 0과 최대 위치인 L도 vector v에 넣어준다.

 

 

#include <bits/stdc++.h>

using namespace std;

int N, M, L;
vector<int> v;

// mid : 휴게소가 없는 구간의 최댓값. 예시) : 20 ~ 50 => 30
bool chk(int mid) {

	// 휴게소 위치는 0부터 시작(1 아님)
	// ※ st = 1로 했었다가 계속 [예제 3]이 틀렸다.
	// → 길이가 1000이면, 0 ~ 1000이라고 생각.
	int st = 0, cnt = 0;

	for (auto i : v) {		
		int temp = 0;

		if((i-st)%mid == 0) temp = (i - st) / mid - 1;
		else temp = (i - st) / mid;

		if (temp < 0) temp = 0;
		cnt += temp;
		
		if (cnt > M) return false;
		
		st = i;
	}

	return true;
}

int ps(int left, int right) {

	int mid, ret = INT_MAX;

	while (left <= right) {

		mid = (left + right) >> 1;

		if (chk(mid)) {
			right = mid - 1;
			//if (code == 0) {
				ret = min(ret, mid);
			//}
		}
		else {
			left = mid + 1;
		}
	}

	return ret;
}

int main(int argc, char** argv)
{
	scanf("%d %d %d", &N, &M, &L);

	v.push_back(L);

	int inpt;
	for (int i = 0; i < N; i++) {
		scanf("%d", &inpt);
		v.push_back(inpt);
	}

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

	printf("%d\n", ps(1, L-1));

	return 0;
}