관리 메뉴

공부공간

BOJ - 1477 ) 휴게소 세우기 본문

구현,시뮬

BOJ - 1477 ) 휴게소 세우기

SangwonSeo 개발자가될수있을까? 2020. 8. 6. 22:56
728x90


 

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

 

1477번: 휴게소 세우기

첫째 줄에 현재 휴게소의 개수 N, 더 지으려고 하는 휴게소의 개수 M, 고속도로의 길이 L이 주어진다. N은 100보다 작거나 같으며, M도 100보다 작거나 같다. L은 100보다 크거나 같고, 1000보다 작거나

www.acmicpc.net


이문제의 정해는 이분탐색으로 찾는것이지만, 정답의 범위가 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트!

728x90

'구현,시뮬' 카테고리의 다른 글

프로그래머스 ) 좌물쇠와 열쇠  (0) 2020.08.16
BOJ - 1560 ) 비숍  (0) 2020.08.12
BOJ - 1477 ) 휴게소 세우기  (0) 2020.08.06
BOJ - 2493 ) 탑  (0) 2020.08.05
BOJ - 17081 ) RPG Extreme  (0) 2020.08.02
BOJ - 1846 ) 장기  (1) 2020.07.29
0 Comments
댓글쓰기 폼