1477_휴게소 세우기 ********

사용 알고리즘: 이분탐색

사용 언어: java

 

대충 푸는 방법은 맞았는데,

한끝차이로 계속 틀림

=> 이거는 내가 이분탐색을 할 때, 미세한 조건을 어떻게 조정해야 할지 몰라서 생기는 문제 같음.

=> 생각하려면 시간이 오래 걸리는데, 테스트에서는 어떠나 싶어서, 케이스를 정해두고 돌려야 하나...

 

package week16;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

//휴게소 세우기
public class Main {
	static int n, m, l, arr[];
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt(); // 휴게소 개수
		m = sc.nextInt(); //더 지으려는 개수
		l = sc.nextInt(); //고속도로 길이
		arr = new int[n+2];
		for(int i=1; i<n+1; i++) {
			arr[i] = sc.nextInt();
		}
		arr[n+1] = l;
		Arrays.sort(arr);
		
		int left = 1;
		int right = l; //휴게소 없는 구간 길이 최대
		while(left <= right) { --> 이것
			int mid = (left + right) / 2;
			int cnt = solve(mid);
			
			if(cnt <= m) {
				right = mid-1; --> 이것
			}
			else {
				left = mid+1; --> 이것
			}
		}
		System.out.println(left); --> 이것
	}

	private static int solve(int mid) {
		int cnt = 0;
		for (int i = 0; i < n+1; i++) {
			int gap = arr[i+1] - arr[i] - 1;
			if(gap < mid) continue;
			else {
				cnt += gap / mid;
			}
		}
		return cnt;
	}

}

 

--> 이것이라고 쓰여있는 곳이 문제의 구간임

 

while(left <= right)	while(left <= right) 혹은 while(left < right)
right = mid-1;	right = mid-1; 혹은 right = mid;
left = mid+1;	left = mid+1; 혹은 left = mid;
System.out.println( right ); ==> (답 출력)	System.out.println(left); 혹은 System.out.println(right); ==> 이건 보통 right가 답이던데....

 

그럼 16개의 경우의 수를.... 돌려본다.....

경험상 최우선적으로 왼쪽에 있는 애들 먼저 돌려보면 되고, 하나씩 바꿔보기...ㅋㅋ...ㅋㅋ..