[Java] 백준 15810번. 풍선공장 (실버2)

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

 

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

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

이분 탐색(Binary Search) 헷갈리지 않게 구현하기

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

 

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

 

 

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);
	}
}