[백준/Java] 15810번 풍선 공장

 

 

문제풀이

이 문제는 이분 탐색으로 풀어야 한다.

 

BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine());

int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int[] arr = new int[N];
long start = Integer.MAX_VALUE;
long end = 0;

1. 문제에서 주어진 입력을 받는다.

이분탐색으로 풀어야하기 때문에 start, end 2개의 포인터를 준비한다.

그리고 왼쪽 포인터인 start에는 최소값이 들어가야하기 때문에 최댓값으로 초기화해준다.

 

st = new StringTokenizer(bf.readLine());
for(int i=0; i<N; i++) {
    arr[i] = Integer.parseInt(st.nextToken());
    start = Math.min(start, arr[i]);
    end = Math.max(end, arr[i]);
}
end = (long) end * M;

2. 반복문을 돌며 start에는 최소값을, end에는 최대값을 담는다.

 

여기서 주의할 점은 최대로 걸리는 시간은 (배열의 최대값) * (풍선의 수)이다.

그렇기 때문에 end에 들어갈 값은 end * M이다.

3 8
5 7 3

 

예제로 예시를 들면,

스태프 수 : 3명

풍선의 개수 : 8개

스태프 3명이 각각 풍선을 만드는데 걸리는 시간 : 5, 7, 3

 

이므로

풍선이 만들어지는데 걸리는 최소값은 3 이고,

풍선이 만들어지는데 최대로 걸리는 시간은 7 * 8 = 56이다.

 

while(start <= end) {
    long mid = (start + end) / 2;

    long sum = 0;
    for(int i=0; i<N; i++) {
        sum += mid / arr[i];
    }

    if(sum >= M) {
        end = mid - 1;
    }else {
        start = mid + 1;
    }
}

3. 반복문을 돌고 while문을 빠져나올 수 있는 조건은 start > end 이다.

 

mid 값은 start + end 를 2로 나눈 값이다.

여기서 mid를 통해 mid 시간 동안 각각의 스태프들은 몇 개의 풍선을 만들 수 있는지 알 수 있다.

이는 mid 에서 arr[i]를 나눈 몫이다.

이를 반복문을 돌며 sum에 더한다.

 

반복이 모두 끝나면 해당 풍선의 개수가 필요한 풍선(M)보다 많은지 적은지 조건문으로 판단한다.

만약 풍선의 개수가 더 많다면 풍선의 개수를 줄여야하기 때문에 end에는 mid-1 을 대입한다.

만약 풍선의 개수가 더 적다면 풍선의 개수를 늘려야하기 때문에 start에 mid+1 을 대입한다.

 

System.out.println(start);

4. 결과를 출력한다.

 

코드

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int[] arr = new int[N];
		long start = Integer.MAX_VALUE;
		long end = 0;
		st = new StringTokenizer(bf.readLine());
		for(int i=0; i<N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
			start = Math.min(start, arr[i]);
			end = Math.max(end, arr[i]);
		}
		end = (long) end * M;
		
		while(start <= end) {
			long mid = (start + end) / 2;
			
			long sum = 0;
			for(int i=0; i<N; i++) {
				sum += mid / arr[i];
			}
			
			if(sum >= M) {
				end = mid - 1;
			}else {
				start = mid + 1;
			}
		}
		System.out.println(start);
	}
}