ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 13702 이상한 술집
    백준/이분탐색 2022. 5. 4. 22:17

     

    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. 이상한 술집

    문제 링크

    ddb8036631.github.io

     

    '백준 > 이분탐색' 카테고리의 다른 글

    20444 색종이와 가위  (0) 2022.06.05
    1561 놀이 공원  (0) 2022.05.28
    12015 가장 긴 증가하는 부분 수열 2  (0) 2022.02.11
    7795 먹을 것인가 먹힐 것인가 (java)  (0) 2022.02.03
    16401 과자 나눠주기  (0) 2021.10.28

    댓글

Designed by Tistory.