[백준 27977번] 킥보드로 등교하기 (C++)

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

27977번: 킥보드로 등교하기

 

#include <iostream>
using namespace std;

int l,n,k,diff = -1;
int arr[100002];

int main() {
	cin >> l >> n >> k;
	arr[0] = 0, arr[n+1] = l;
	for(int i = 1; i <= n; i++){
		cin >> arr[i];
	}
	for(int i = 1; i <= n+1; i++){
		diff = max(diff,arr[i]-arr[i-1]);
	}
	
	int ans = l;
	int left = diff, right = l;
	while(left <= right){
		int mid = (left+right)/2;
		int cnt = 0;
		int tmp = 0;
		for(int i = 1; i <= n+1; i++){
			if(arr[i]-tmp > mid){
				cnt++;
				if(arr[i]-tmp == mid) tmp = arr[i];
				else tmp = arr[i-1];
			}
		}
		if(cnt > k) {
			left = mid + 1;
		}
		else {
			right = mid - 1;
			ans = min(ans,mid);
		}
	}
	cout << ans;
}

 

 

막힌 부분

1. 이분 탐색 범위 설정을 구체적으로 하는게 매우 중요함. (left, right 초기값 설정)

대충 0과 최댓값으로 하지말고 초기값을 구체적으로 잡을 것

2. arr[n+1]에 값을 넣었으면서 배열은 크기는 100001에서 안늘려 무수히 많은 W/A를 찍어냄.