13702 이상한 술집

 

1. 문제 풀이 

 

이분탐색으로 풀면 된다.

코드를 설명하겠다.

 

1) 예제 

문제에 나온 예제를 살펴보자.

2 3

702

429

 

2) 변수 설명 

 

N(주문한 막걸리 주전자 개수) : 2,

K(친구들의 수) : 3 

주전자 용량 : 702, 429 => drink 배열에 입력

 

이분탐색에 필요한 변수 

left = 0, right = 702 (주전자 용량 중 제일 큰 값) => mid = (0+702)/2 = 351 

 

이분탐색을 시작한다.

 

			for(int i=0; i<N; i++) {
				count+=drink[i]/mid; 
			}

위의 코드에서 볼 수 있듯이,

count 변수는 각각의 주전자 용량을 mid 값으로 나눈 값 중 정수부분의 합이다.

count 변수가 int 형 이므로 소수점은 버려지고 정수만 더해진다.

 

즉, 맨 처음에 mid = 351 인데,

 

1) 주전자 용량 : drink[0] = 702

=> 702/351 = 2

=> count = 2

즉, 하나의 주전자에 들어있는 702 ml 막걸리를 351ml씩 나눠주면 2번 나눠줄 수 있다.

 

2) 주전자 용량 : drink[1] = 429

=> 429/351 = 1.22222

=> count = 3 (1.22222.......... 이지만 정수만 더해짐)

 

우리는 최종적으로, count = K 를 만족시키는 최대 막걸리 용량을 이분탐색으로 찾으면 된다.

 

 

 

3) 이분탐색

 

그러면 이제 제대로 이분탐색을 해보자.

 

1) left = 0, right = 702, mid = 351 // 위에서 설명함

=>

702/351 = 2,

429/351 = 1.22

최종 count = 3

 

현재 count = 3 = K 를 만족하지만, 문제에서 최대 막걸리 용량을 출력하라고 했다.

count = 3 을 만족하는 더 많은 막걸리 용량이 있을 수 있다.

그래서 이분탐색이 이어진다.

 

left, right, mid가 막걸리 용량을 의미하는데,

left 변수 값을 증가시키거나, right 변수 값을 줄이는 두가지 경우가 있다.

 

 

			
			if(count >= K) {
				left = mid+1;
				
			}else{
				right = mid-1;
			
			}

 

 

여기서는

용량이 늘어나는 쪽, left = mid +1 로 가야 된다.

=> left = 352

 

2) left = 352, right = 702, mid = 527

이때는 count = 1 이 된다.

 

그러면, count = 3이 만족되게 하려면,

count = ('drink[0]/ mid' 정수부분) + ('drink[1]/ mid' 정수부분)

이므로, mid 를 줄여야 한다.

그러려면 right = mid-1 쪽으로 간다.

 

3) left = 352, right = 526, mid = 439

이때도 count =1 이 된다.

 

 

이런 작업을 반복하다가,

8번째가 되면,

8) left = 352, right = 355, mid = 353

이때도 count =2 이다.

 

9) left = 352, right = 352, mid = 352

이때도 count =2 가 된다.

 

그러면 right = mid -1 이 되는데, 이때 right = 351 이 된다.

 

그러면 while 문의 조건인 left <= right 조건이 만족이 안돼서

while 문을 탈출한다.

 

그리고 최종적으로 right = 351 을 답으로 출력한다.

 

 

2. 헷갈렸던 부분

 

 

내가 고민했던 부분이 이 부분이다.

 

1) 정답이 mid 라고 생각했던 이유 

 

 

나는 right 가 아닌 mid가 우리가 찾는 정답, 즉 최대 막걸리 용량을 나타낸다고 생각했다.

 

 

			for(int i=0; i<N; i++) {
				count+=drink[i]/mid; 
			}

count 값은 위와 같이 구해진다.

 

위에 설명했듯이, 이분탐색 맨 처음에 

left = 0, right = 702, mid = 351, drink[0] = 702, drink[1]= 429 이다.

 

mid = 351 인 막걸리 용량만큼

drink[0] = 702 인 주전자 용량을 나누면 (702/351 =2)

2명에게 나눠줄 수 있고,

 

drink[1] = 429 인 주전자 용량을 나누면 (429/351 = 1.2222)

1명에게 나눠줄 수 있다.

 

따라서 총 3명의 친구에게 나눠줄 수 있고, 이는 K(친구 수) = 3 과 같다.

문제에서 정답으로 K명에게 나눠줄 수 있는 최대 막걸리 용량을 출력하라고 했다.

그래서 나는 mid = 351만큼씩 나눠주면 3명에게 나눠줄 수 있듯이,

count = K를 만족하는 최대 mid 값을 정답으로 제출해야 된다고 생각했다.

 

주전자 용량(drink[i])을 right 가 아니라 mid 로 나누기 때문이다.

 

그런데 right 가 답이다.

 

왜 그런지 그림으로 살펴보겠다. 

 

2) 정답이 right 인 이유

 

위에서 계속 설명한 아래 예제에 대한 설명이다. 

2 3

702

429

 

풀이 과정은 위에서 설명했으므로 간단하게 설명하며 넘어가겠다.

 

 

그림에 mid 값을 나타내 보았다.

(첫 번째, 두 번째, 여덟 번째, 아홉 번째 mid 값을 나타낸 것이다.

맨 처음 mid = 351 에서 두번째 527이 된 후에는 계속 mid 값이 줄어들어서 화살표로 줄어듦을 표현했다.)

 

1) 맨 처음 left = 0, right = 702, mid = 351 이다.

이때 count = 3 으로 K와 같다.

 

그런데, count = 3 을 만족하는 더 큰 막걸리 용량을 찾기 위해 mid 값을 527로 증가시켰다.

 

2) left = 352, right = 702, mid = 527

=> count = 1 

// K = 3과 같지 않다.

 

3) mid = 439

=> count = 1

 

4) mid = 395

=> count = 2

 

...

 

8) mid = 353

=> count = 2

 

9) mid = 352

=> count = 2

 

10) 이때는 left = 352, right = 351 이다.

left> right 가 되어서

while 문을 탈출한다.

 

즉, 맨 처음 mid = 351 일때 count = 3 으로 K 와 일치했지만,

더 큰 막걸리 용량을 찾기 위해 mid 값을 증가시켰다.

그런데, count =1 이 되어, mid값을 점점 줄여야 했고,

 

줄이다 줄이다, mid = 352 가 되었을 때도 count =2 가 되어서

count = 3을 만족하지 못하게 된 것이다.

 

결국 맨 처음 mid = 351 일때가 count = 3을 만족하는 최대의 값이였던 것이다.

그런데 첫 번째

left = 0, right = 702, mid = 351 이후 

left = mid +1 = 352 가 되어서, 9번째까지 left = 352가 된다.

우리가 원하는 정답은 351이고, right 가 left 보다 작아진 그 때, 즉 351이 되었을 때 while문을 탈출하고

이 값을 최종 답으로 제출하는 것이다.

 

그래서 right 가 답이 된다. 

 

 

3. 최종 코드

 

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 br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " " );
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		long drink [] = new long [N];
		long right = 0;
		
		for(int i=0; i<N; i++) {
			drink[i] =Integer.parseInt(br.readLine());
			right = Math.max(drink[i], right);
		}
		
		long left = 0;
		long mid = 0;
		
		while(left <= right) {
			
			int count = 0;
			mid = (left + right)/2;
			
			
			if(mid == 0) {
				break;
			}
			
			
			for(int i=0; i<N; i++) {
				count+=drink[i]/mid; 
			}
			
			
			if(count >= K) {
				left = mid+1;
				
			}else{
				right = mid-1;
			
			}
		}
		
		
		System.out.println(right);
	}
}

 

 

참고 블로그 : 

https://ddb8036631.github.io/boj/13702_%EC%9D%B4%EC%83%81%ED%95%9C-%EC%88%A0%EC%A7%91/

[백준] 13702. 이상한 술집