[백준] 28305 - 세미나 배정

[문제]

---

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

[풀이]

---

각 날에 진행되는 세미나 수를 k로 정하고 배정을 할 수 있는 지 없는 지 판단할 수 있다.
$a_i$ 를 오름차순으로 정렬하여 이분탐색을 적용하면 $O(NlogN)$ 으로 풀 수 있다.

func에서 dp 는 각 세미나의 시작 날짜를 저장하고 있다.
하루에 최대 k개의 세미나가 배정되려면 우선 k개의 세미나가 존재해야하므로, i<k 인 i번째 세미나는 최대한 먼저 시작할 수 있도록 한다.
1일차부터 배정할 수 있으므로 max를 취한다.
i>=k 인 i번째 세미나는 i-k번째 세미나의 시작시간 + t와 비교하여 저장할 수 있도록 한다.

대강 세미나 시작시간을 정하면, $a_i$가 범위 안에 속하는 지 확인하면 된다.

[코드]

---

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	
	static int n;
	static int t;
	static int[] a;
	
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int[] input = getInt(scanner.nextLine());
		n = input[0];
		t = input[1];
		a = getInt(scanner.nextLine());
		Arrays.sort(a);
		
		int lo = 0;
		int hi = n+1;
		while (lo + 1 < hi) {
			int mid = (lo+hi)/2;
			if (func(mid)) {
				hi = mid;
			} else {
				lo = mid;
			}
		}
		System.out.println(hi);
		scanner.close();
	}

	public static boolean func(int k) {
		int[] dp = new int[n];
		for (int i=0; i<n; i++) {
			dp[i] = a[i];
		}
		for (int i=0; i<n; i++) {
			if (i < k) {
				dp[i] = Math.max(a[i] - t + 1, 1);
				continue;
			}
			dp[i] = Math.max(dp[i-k] + t, Math.max(a[i]- t + 1 , 1));
		}
		for (int i=0; i<n; i++) {
			if (dp[i] > a[i]) return false;
		}
		return true;
	}
	
	public static int[] getInt(String content) {
		return Arrays.stream(content.split(" "))
				.mapToInt(Integer::parseInt).toArray();
	}
}