내일은 알고리즘

https://programmers.co.kr/learn/courses/30/lessons/43238

이분탐색의 기본적인 응용문제입니다.

가능한 정답의 최소시간 = 1과 확실하게 가능한 정답중의 하나 = ((대기자의 수 / 심사관의 수) + 1 ) * 가장 느린 심사속도 두개를 시작점으로 해서 이분탐색을 돌리면 됩니다.

이분 탐색 문제는 언제나 탐색을 멈추는 조건을 정하는게 어려운데, 문제가 보통 정답의 최댓값이나 최솟값을 요구합니다. 우리는 문제에 따라 확실하게 가능한 정답과 확실하게 정답이 아닌 것+1을 줄여가다가 둘이 겹치는 곳에서 문제가 요구하는 답을 찾을 수 있습니다.

public class q43238_Programmers_입국심사 {

	public static void main(String[] args) {

		int n = 6;
		int[] times = { 7, 10 };

		System.out.println(solution(n, times));
	}

	private static long solution(int n, int[] times) {
		long answer = 0;

		long max = 0;

		for (int t = 0; t < times.length; t++) {
			max = Math.max(max, times[t]);
		}

		long left = 1;
		long right = ((n / times.length) + 1) * max;

		while (left < right) {
			long center = (left + right) / 2;
			long count = 0;

			for (int t = 0; t < times.length; t++) {
				count += (center / times[t]);
			}
			
			if(count >= n) {
				right = center;
			}else {
				left = center + 1;
			}

		}

		answer = right;
		return answer;
	}
}

문제풀이 루틴에 관한 글은
https://nodingco.tistory.com/23  <- 여기를 참고해주세요!

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

JAVA로 푼 문제를 Python으로 다시 작성한 문제입니다.

풀이방법과 주의사항, JAVA 정답 코드를 보고 싶으신 분은 아래 링크를 확인해주세요!

https://nodingco.tistory.com/28

import sys

N,M = map(int, sys.stdin.readline().split(' '))
staffs = list(map(int, sys.stdin.readline().split(' ')))

left = 0
right = min(staffs) * M

while(left+1 < right):
    center = (left + right)//2
    balloon = 0

    for n in range(N):
        balloon += center//staffs[n]
    
    if(balloon >= M):
        right = center
    else :
        left = center

print(right)

문제풀이 루틴에 관한 글은
https://nodingco.tistory.com/23  <- 여기를 참고해주세요!

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

1. 이해 (5분) - 1분

문제도 깔끔하고 이해에 어려운 부분도 없어 금방 이해를 마쳤습니다.

정답이 가능한 범위가 무척 넓은데 여기서 이분 탐색 문제임을 유추했습니다. 

(최악의 경우 스태프 1명이 100만분 마다 풍선 하나를 만들고, 이를 100만 개 불어야 하면.... 1조가 정답이다!) 

2. 계획 (5분) - 1분

문제를 이해한 대로 이분탐색을 통해 풀이할 계획을 세웠습니다.

이분 탐색에선 초기값을 잡는 것이 중요한데, 정답의 최댓값은 가장 빨리 풍선을 부는 스태프가 전부 부는 경우보다 작기 때문에 그 값을 최댓값으로 놓았습니다.

최솟값과 최댓값 사이의 중간값을 잡고, 이 값이 정답이 가능한 수인지를 확인합니다.

중간값을 각 스태프들이 풍선을 부는데 걸리는 시간으로 나누면 그 시간에 스태프들이 불 수 있는 풍선의 개수가 나오고 그 값을 전부 합치면 이 시간에 가능한 풍선의 개수가 나옵니다! 

풍선의 갯수를 주어진 M과 비교해서 크거나 같으면 정답이 중간값이거나 더 아래에 존재하므로 이분 탐색의 최댓값을 중간값으로 바꾸고 풍선이 부족하면 중간값 위에 정답이 존재하므로 최솟값을 중간값으로 바꿔줍니다.

3. 검증 (5분) - 3분

이분탐색 문제는 기본적으로 정답의 범위가 크기 때문에 오버플로우가 자주 발생합니다.

본 문제에서도 int의 범위는 넘을것이 딱 보였기 때문에 문제 전체에서 long을 사용하기로 했습니다.

(JAVA 언어의 long은 C, C++ 등의 longlong과 같습니다.)

4. 풀이 (30분) - 8분

이분탐색 코드는 생각해내기가 어렵지 코드량과 작성 자체는 어렵지 않기 때문에 금방 작성을 마쳤습니다.

하지만 이분탐색의 마수가 또다시 저를 괴롭히니...

5. 채점, 디버깅 (+20분)

여러 번의 오답을 맞으면서 디버깅 시간이 길어졌습니다.

문제 풀이의 접근과 코드의 논리에는 문제가 없으나, 이분 탐색의 양 극단의 값 중에서 정답을 고르는 부분에 문제가 있어 예외가 발생하는 것 같았습니다. (테스트 케이스 62%쯤에서 오답 처리되었습니다.)

검색을 통해 유익한 글을 찾아... 이분 탐색을 다시 이해하고 코드를 제출해 통과했습니다.

핵심 로직은 건드린 게 없으니, 예상대로 정답을 고르는 부분에서 문제가 있었던 것 같습니다.

https://www.acmicpc.net/blog/view/109

상당히 유익한 글이고 이분 탐색 문제 풀이에서 발생하는 오답을 잡아주기 때문에 저와 비슷한 어려움을 겪으시는 분들은 꼭 읽어보시길 추천드립니다.

구현은 쉽지만 오류 찾기가 어려운 이분 탐색 문제였습니다. 감사합니다!

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

public class Main {
	static StringTokenizer st;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		st = new StringTokenizer(br.readLine());
		long N = Integer.parseInt(st.nextToken());
		long M = Integer.parseInt(st.nextToken());
		long[] staffs = new long[(int) N];

		st = new StringTokenizer(br.readLine());
		long min = Integer.MAX_VALUE;
		for (int n = 0; n < N; n++) {
			staffs[n] = Integer.parseInt(st.nextToken());
			min = Math.min(min, staffs[n]);
		}
		
		long left = 0;
		long right = min * M;
		
		while(left+1 < right) {
			long center = (left + right)/2;
			long balloon = 0;
			
			for (int n = 0; n < N; n++) {
				balloon += (center / staffs[n]);
			}
			
			if(balloon >= M) {
				right = center;
			}else {
				left = center;
			}
		}
		
		System.out.println(right);
	}
}