백준16401. 과자 나눠주기

✔️ 문제 분석

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

 

매개변수탐색에서는 start, end, mid의 범위 설정이 중요하다.

평소 익숙한 매개변수탐색 로직을 작성해 제출했지만 계속 틀려 게시판의 예외 케이스를 보고 틀렸다는 것을 깨닫게 되었다. 

 

💣 틀린 코드 

평소 start < end 그리고 start를 출력하는 방식으로 매개변수탐색 알고리즘을 풀어왔다. 

long start = 1;
long end = snacks[N-1];
long max = 0;
while (start < end) {
    long mid = (start+end+1)/2;

    if(cutting(mid)){
       start = mid;
       max = mid;
    }
    else {
       end = mid-1;
    }
}
if (max == 0) {
   System.out.println(0);
}
else System.out.println(start);

 

input 케이스

3 4
1 1 1 1

output:0
answer:1

 

1️⃣ while 조건문 수정

start를 1, end를 1로 잡게되면 while(start<end) 조건에 처음부터 false가 되서 0이 출력된다. 

그래서 while(start<=end)로 수정했다. 

 

2️⃣start = mid 수정

start = mid 를 하면 위의 input일 경우 start도1, mid도 1이면 start=1이라는 무한루프를 돌게 된다.

그래서 start = mid+1을 했다.

start = mid +1 을 하면 start = 2가 되고, while문의 조건인 (start<=end) 조건에서 start = 2, end = 1이므로 while문이 종료된다. 

 

---

✅ 통과 코드 

import java.io.*;
import java.util.*;

public class Main {
    static int M, N;
    static int[] snacks;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());

        snacks = new int[N];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            snacks[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(snacks);
        long start = 1;
        long end = snacks[N-1];
        long max = 0;
        while (start <= end) {
            long mid = (start+end)/2;

            if(cutting(mid)){
                start = mid+1;
                max = mid;
            }
            else {
                end = mid-1;
            }
        }
        if (max == 0) {
            System.out.println(0);
        }
        else System.out.println(max);

    }

    public static boolean cutting(long mid) {
        int cnt = 0;

        for (int i = 0; i < N; i++) {
            cnt += (snacks[i]/mid);
        }
        if (cnt >= M) {
            return true;
        }
        return false;
    }
}

---

💡tips!

while(start <= end) 의 경우

• (start+end)/2 또는 (start+end+1)/2 둘 다 사용 가능하다.
• start = mid +1, end = mid-1로 설계한다. 

B.U.T

while(start < end) 의 경우

• (start+end+1)/2
• start = mid , end = mid-1로 설계하는 경우가 많다.