[BOJ 16401] 과자 나눠주기

시간복잡도

시간제한: 1초, 메모리: 128MB

• 조카 수 M (1 ~ 1,000,000)
• 과자 수 N (1 ~ 1,000,000)
• 과자의 길이 L (1 ~ 1,000,000,000)

가능한 시간복잡도: O( log scale * M or N)

 

유형 분석

Goal: 조카 1명에게 줄 수 있는 막대과자의 최대길이

 

조카수: 4 과자수: 3
과자N개의 길이: [10 10 15]

 

 

 

 

 

 

 

과자N개의 길이에 대해, 특정 x길이로 나눈 몫들의 합을 count라 하자.

 

count < 조카수라면, 모든 조카에게 나눠줘야한다는 조건을 만족하지 못하고 무조건 더 작게 잘라야 한다. (※ 모든 조카에게 나누어줘야하기 때문) 아래의 그림을 살펴보면 이해가 될 것이다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

mid 값 이상의 값은 모두 조건을 만족하지 못하는 F A L S E 영역이다. mid값으로 막대를 나눴을 때, 모든 조카에게 나눠주지 못한다면, 더 큰 값으로 막대를 나누면 당연히 모든 조카에게 나눠주지 못할 것이다.

 

즉, mid값에 대한 count < 조카수라면

right = mid - 1

로 index를 컨트롤하고 탐색 후보군에 대해 마저 탐색을 진행하면 된다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

mid 값 이하의 값은 모두 조건을 만족하는 T R U E 영역이다. mid값으로 막대를 나눴을 때, 모든 조카에게 나눠줄 수 있다면, 더 작은 값으로 막대를 나눠도 당연히 모든 조카에게 나눠줄 수 있을 것이다.

 

즉, mid값에 대한 count >= 조카라면

result = mid

left = mid + 1

 

mid값은 정답 후보이므로 result에 등록하고, 후보군을 탐색하기 위해 인덱스를 컨트롤하자.

result로 등록하고, left = mid이 아닌 left = mid + 1을 한 이유는 무한루프를 방지하기 위함이다.

 

 

위의 과정을 통해, 파라매트릭 서치가 가능한 조건임을 확인했다.

• [ T T T T T T T T F F F F F F F F] 형태로 정렬된 상태여야만 파라매트릭 서치가 가능하다.

 

참고로 아래와 같은 힌트들로 파라매트릭 서치를 의심해볼 수 있다.

1. Input Size가 크고
2. Log scale을 고려해야하고
3. 최대 or 최소를 묻고
4. 파라매트릭 서치가 가능한 상태일 때

 

유형: 파라매트릭 서치

시간복잡도: O (log 막대길이 * 과자개수) = O (log 1,000,000,000 * 1,000,000) = O( 9백만 )으로 가능

 

 

파라매트릭 서치 설계

if(count(mid) < 조카수) {
	right = mid - 1;
} else {
	result = mid;
    left = mid + 1;
}

 

 

 

코드

import java.io.*;
import java.util.*;

public class Main {
	private static int M, N, maxLength;
	private static int[] snackLengths;

	public static void main(String[] args) throws IOException {
		input();
		System.out.println(parametricSearch());
	}
	
	private static long parametricSearch() {
		long left = 1;
		long right = maxLength;
		long result = 0;
		while(left <= right) {
			long mid = (left + right) / 2;
			if(calculateEatPeopleCount(mid) < M) {
				right = mid - 1;
			} else {
				result = mid;
				left = mid + 1;
			}
		}
		return result;
	}
	
	private static int calculateEatPeopleCount(long length) {
		int count = 0;
		for(int snackLength: snackLengths) {
			count += snackLength / length;
		}
		return count;
	}
    
    	private static void input() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		M = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(st.nextToken());
		snackLengths = new int[N];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			snackLengths[i] = Integer.parseInt(st.nextToken());
			maxLength = Math.max(maxLength, snackLengths[i]);
		}
	}
}