[백준 15810 / 풍선 공장 / JAVA / 이분 탐색]

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

15810번: 풍선 공장

 

문제 접근

다른 건 다 제대로 적어놓고 범위를 지정하는데서 애 먹었다.

left는 0이나 1로 해도 통과

right의 값을 현재 풍선 만드는데 가장 오래 걸리는 사람의 시간 *  풍선 갯수로 잡아줘야한다.

 

내가 적은 코드 상엔 시간이 정렬된 배열의 마지막 인덱스를 가져와서 최소 풍선 갯수랑 곱한 값으로 right값을 지정해놨는데

이론상 최대 시간은 1000000(풍선 최대 갯수) * 1000000(풍선 만드는 최대 시간) = 1조이다.

right의 값을 (long)1000000 * (long)1000000로 지정해줘도 문제는 풀린다.

 

★ right를 long으로 선언해도 연산하는 숫자들도 long으로 지정해줘야 하더라

 

이후 while문에서 시간 배열의 요소들을 mid(현재 걸리는 시간)로 나눠준 후 만들 수 있는 풍선의 갯수를 합산

합산된 풍선 갯수가 최소 갯수를 충족하면 그 때의 시간을 저장하고 더 적은 시간으로 조건을 충족하는지 탐색하기 위해 right의 시간을 변경

 

최소 갯수를 충족하지 못하면 left의 시간을 변경시켜서 조건을 충족시키는 시간을 탐색하도록한다.

 

그렇게 left가 right보다 커져서 범위를 다 탐색했을 때 가장 최근에 저장된 시간을 출력해준다.

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[] time = new int[N];
	      st = new StringTokenizer(br.readLine());
	      
	      for(int i=0; i<N; i++) time[i] = Integer.parseInt(st.nextToken());
	      Arrays.sort(time);
	       // 최대로 걸릴 수 있는 시간을 문제 읽고 잘 생각하자
	      // 직원 한 명이 최대 시간으로 최대 갯수의 풍선을 만들어야 할 때가 최대 시간
	      long left = 1;
	      long right = (long)time[time.length-1] * M; // right를 long으로 잡아도 연산하는 숫자들도 long으로 지정해줘야..
	      long result = 0;
	      
	      while(left <= right) {
	    	  long mid = (left + right ) / 2;
	    	  long count = 0;
	    	  
	    	  for(int i=0; i<N; i++) {
	    	    count += mid / time[i];	  
	    	  }
	    	  
	    	  if(count >= M) {
	    		  result = mid;
	    		  right = mid - 1;
	    	  }
	    	  else if(count < M) {
	    		  left = mid + 1;
	    	  }
	      }
	      System.out.println(result);
	}
}