99클럽 코테 스터디 11일차 TIL - 과자 나눠주기(이진탐색)

문제: https://www.acmicpc.net/problem/16401
알고리즘 분류: 이분 탐색, 매개 변수 탐색

문제 파악

주어진 과자들을 특정 길이로 잘라서, 조카들에게 나눠줄 수 있는 최대 길이를 찾는 문제

• M명의 조카와 N개의 과자

• 모든 조카에게 같은 길이의 과자를 나눠줘야 한다

• 과자는 여러 조각으로 나눌 수 있지만, 합칠 수는 없다

• 조카 1명에게 줄 수 있는 과자의 최대 길이 구하기

접근 방법: 이진 탐색 (Binary Search)

결정 문제(Decision Problem)
"과자 길이가 mid일 때, M명의 조카에게 나눠줄 수 있어?"

1. 가능한 과자 길이의 범위: 1 부터 가장 긴 과자 길이까지

2. 특정 길이 mid로 자를 때, 만들 수 있는 과자 조각의 수 count 계산

3. count가 M 이상 ➡️ 더 긴 길이를 찾아

4. count가 M 미만 ➡️ 더 짧은 길이 찾아

예시 ✅

조카M 3명, 과자길이snacks = [1,2,3,4,5,6,7,8,9,10]

이진 탐색 과정:

1. 첫 번째 시도 할 과자길이 mid = 5 (1~10의 중간값)
   총 조각 수count = 7개 >= 3명(가능) → 더 긴 길이로 시도 → left = mid + 1 = 6, right = 10

2. 두 번째 시도 할 과자길이 mid = 8 (6~10의 중간값)
   총 조각 수count = 3개 >= 3명(가능) → 더 긴 길이로 시도 → left = mid + 1 = 9, right = 10

3. 세 번째 시도 할 과자길이 mid = 9 (9~10의 중간값)
   총 조각 수count = 2개 < 3명(불가능) → 더 짧은 길이로 시도 → left = 9, right = mid - 1 = 8 → 종료

내 코드

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

const [M, N] = input[0].split(' ').map(Number); 
const snacks = input[1].split(' ').map(Number); 

const findMaxSnackLength = (nephews, snacks) => {
    let left = 1;
    let right = Math.max(...snacks);
    let result = 0;
    
    while (left <= right) {
        const mid = Math.floor((left + right) / 2); 
        let count = 0;
        for (const snack of snacks) {
            count += Math.floor(snack / mid); 
        }
        
        if (count >= nephews) {
            result = mid; 
            left = mid + 1; 
        } else {
            right = mid - 1;
        }
    }
    
    return result;
}

const answer = findMaxSnackLength(M, snacks);
console.log(answer);

시간 복잡도

• 이진 탐색: O(log(max_length))
• 각 단계에서 모든 과자를 검사: O(N)
• 전체 시간 복잡도: O(N * log(max_length))

과자의 최대 길이가 10^9이므로, 이진 탐색은 최대 약 30번 정도의 반복으로 결과 도출

참고
https://bedecked-operation-4d1.notion.site/99-11-TIL-16401-1d5eb405261e80c1a245db9ed837464f