[백준 15810번] 풍선 공장 - java

문제 설명

1. N명의 스태프, 만들어야 하는 풍선M이 주어진다.

2. 각 N명의 스태프가 1개의 풍선을 부는 데 들어가는 시간이 주어진다.

3. M개의 풍선을 만드는 최소시간을 구하라

 

풀이 과정

 1. 이분탐색이다.

 2. 이분탐색 -> Long타입에 주의하자...허헣 풀이방법 자체는 이전하고 별반 차이는 없다.

      - 몇 분의 시간이 주어지고, 해당 시간동안 몇개의 풍선을 불 수 있는지 구하면 된다.

 3. 왼쪽 -> 0으로 시작하면 된다.

 4. 오른쪽 -> 풍선 부는데 제일 오래걸린 시간 * 풍선 개수면 일단 가장 오래걸리는 시간이 구해진다.

 5. 만약 3, 5, 6분마다 한개씩 풍선을 만든다고 가정하면 7분이 주어지면 각각 2, 1, 1개를 만들것이다.

 6. 현재 시간에 분 최대 풍선개수가 원하는 개수보다 적으면 답이 아니다. 

 7. 일단 지금 원하는 것보다 많은 풍선을 불었으면 저장해주고, 더 빠른 시간을 구하러 떠난다.

 8. 이분탐색이 끝나면 정답을 return해준다.

코드

	import java.util.*;
	import java.io.*;
	public class Main {
	public static void main(String args[]) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer st = new StringTokenizer(br.readLine());
	int N = Integer.parseInt(st.nextToken());
	int M = Integer.parseInt(st.nextToken());
	int num[] = new int[N];
	int max = 0;
	StringTokenizer st2 = new StringTokenizer(br.readLine());
	for(int i=0; i<N; i++){
	num[i] = Integer.parseInt(st2.nextToken());
	max = Math.max(max, num[i]);
	}
	long left = 0;
	long right = (long)max*M;
	long ans = 0;
	while(left <= right){
	long mid = (left+right)/2;
	long sum = 0;
	for(int i=0; i<N; i++){
	sum += (long)mid/num[i];
	}
	if(sum < M){
	left = mid+1;
	}else{
	right = mid-1;
	ans = mid;
	}
	}
	System.out.println(ans);
	}
	}

view raw 풍선공장.java hosted with ❤ by GitHub

이분탐색은 참...주기적으로 하나씩 해줘야할것같다.