BOJ - 1477 ) 휴게소 세우기

---

 

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

1477번: 휴게소 세우기

---

이문제의 정해는 이분탐색으로 찾는것이지만, 정답의 범위가 0-1000사이 이므로 

 

휴게소 사이의 거리의 최솟값을 시작값으로, 최댓값을 종료값으로하고 

 

FOR문으로 하나하나검사해도 풀린다.

 

시작과 끝 0 과 L 위치의 휴게소가 있다고 생각하고

 

각 휴게소 사이의 거리를 측정한다. => 최솟값과 최댓값사이의 값하나가 휴게소의 거리라 생각하고,

 

몫 -1 ( 나누어 떨어질때 ) Or 몫 의 값을 더하면서 M이 초과하면 불가능이라 판단한다.

 

그렇게 바텀업으로 진행하였을때 최초 M을 만족하는 거리가 정답이다.

 

 

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class 휴게소세우기 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int l = Integer.parseInt(st.nextToken());
		int num[] = new int[n];
		st = new StringTokenizer(br.readLine());
		for(int i = 0 ; i < n ; i++) num[i] = Integer.parseInt(st.nextToken());
		Arrays.sort(num);
		int dist[] = new int[n+1];
		int distmax = -1;
		int distmin = 1001;
		for(int i = 0 ; i < n ; i ++) {
			if(i == 0) {
				dist[0] = num[0];
				distmax = distmax > dist[0] ? distmax : dist[0];
				distmin = distmin < dist[0] ? distmin : dist[0];
 			} else {
				dist[i] = num[i] - num [i-1];
				distmax = distmax > dist[i] ? distmax : dist[i];
				distmin = distmin < dist[i] ? distmin : dist[i];
			}
		}
		dist[n] = l-num[n-1];
		distmax = distmax > dist[n] ? distmax : dist[n];
		distmin = distmin < dist[n] ? distmin : dist[n];
		int answer = 0;
		for(int i = distmin ; i <= distmax ; i++) {
			int cnt = 0;
			boolean impossible = false;
			for(int j = 0 ; j <= n ; j++) {
				int number = dist[j];
				if(number <= i ) continue;
				if(number%i!=0) {
					cnt += (number/i);
				} else {
					cnt += (number/i)-1;
				}
				if(cnt >m) {
					impossible = true;
					break;
				} 
			}
			if(!impossible) {
				answer =i;
				break;
			}
		}
		System.out.println(answer);
	
	}

}

---

1트!