[C++] 99클럽 코테 스터디 11일차 TIL + 과자 나눠주기(백준 16401번)

✅ 오늘의 학습 키워드

• 이분 탐색 (Binary Search) or 이진 탐색
• 결정 문제 (Decision Problem)
• 단조성 (Monotonicity) - 증가 / 감소 

---

✅ 공부한 내용

✔️ 문제 요약

(백준 문제 링크: https://www.acmicpc.net/problem/16401)

명절에 조카들에게 막대 과자를 모두 나눠주는 문제다. 조건은 다음과 같다.

1. M명의 조카들에게 동일한 길이의 과자를 나눠줘야 한다.
2. 과자는 여러 조각으로 나눌 수 있지만, 합칠 수는 없다. (과자의 길이는 양의 정수)
3. 조카 1명에게 줄 수 있는 가장 긴 과자의 길이를 찾아야 한다.

✔️ 풀이 로직

이 문제는 길이가 L인 과자를 M명의 조카에게 모두 나눠줄 수 있을까? 라는 결정 문제(Decision Problem)로 생각하고 길이 L에 대한 단조 증가/감소 특성은 단조성(Monotonicity)이라고 하며 이분탐색의 조건이라고 한다. 그래서 이 문제는 이분 탐색을 활용해서 해결 할 수 있다.

1. Bool 함수를 사용하여 판단하기
   • 길이가 L인 과자를 M명의 조카에게 모두 나눠줄 수 있을까? 라는 True / False를 판단하자.
   • 만약 모든 조각 수의 합계가 조카의 수 이상이면 나눠줄 수 있다. (true)
   • 조카 수보다 적으면 나눠 줄 수 없다. (false)
2. 이진 탐색 적용하기
   • 탐색 범위는 0부터 가장 긴 과자의 길이까지다.
   • 초기값: left = 0, right = 가장 긴 과자의 길이
   • 중간값(mid)를 사용하여 계산하고, 이 길이로 모든 조카에게 나눠줄 수 있는지 확인한다.
     • → 가능하다면 결과값(result)을 mid로 갱신하고, 더 긴 길이를 시도한다 (left = mid + 1).
     • → 불가능하다면 더 짧은 길이를 시도한다 (right = mid - 1).
   • 3반복 조건: left ≤ right일 동안 계속 탐색을 진행한다.
   • 최종적으로 result에 저장된 값이 조카 한 명에게 줄 수 있는 최대 길이가 된다.

---

✅ 오늘의 회고

- 😳 어떤 문제가 있었고, 나는 어떤 시도를 했는지

처음에는 문제를 보고 어떻게 접근해야 할지 감이 잡히지 않았다. 완전 탐색으로 모든 가능한 길이를 시도해볼까 생각했으나, 과자 길이가 최대 10억까지라서 시간 초과가 발생할 것이 분명했다. (사실 찾아봄 ㅎ..)

 

• 시간 복잡도: O(N * log(최대 과자 길이))
• 과자 길이가 최대 10^9이므로 모든 가능성을 일일이 확인하는 것은 불가능(완전 탐색 X)
• 이분탐색은 log(10^9) ≈ 30번의 반복으로 최적해를 찾을 수 있다.

 

- 🤔 어떻게 해결했는지 

문제의 특성을 분석해보니 "과자 길이가 L일 때 조카들에게 나눠줄 수 있는가?"라는 생각으로 바꿀 수 있었다. 이런 판단 문제는 이진 탐색으로 효율적으로 해결할 수 있다는 것을 알았다. 결정적이었던 것은 "어떤 길이로 나눌 수 있다면, 그보다 작은 길이로도 당연히 나눌 수 있다"는 것을 보고 생각했다.

- 🤩 무엇을 새롭게 알았는지

여전히 문제를 보고 어떤 알고리즘을 사용해야할지 감이 안온다..

실제 코딩 테스트에서는 이런 패턴을 빠르게 파악하는 것이 중요하다는 것을 느꼈다.
문제의 특성을 찾아내고, 적절한 알고리즘(이진 탐색)을 적용하는 연습이 필요해보인다. 

 

이분탐색과 매개변수탐색(Parametric Search)에 대해 좀 더 알아봐야겠다...!!

---

✅ 전체 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 주어진 길이로 과자를 나눴을 때 몇 명의 조카에게 줄 수 있는지 확인하는 함수
bool giveSnack(const vector<int>& snacks, int m, int length) {
    if (length == 0) return true; // 길이가 0이면 항상 가능

    int count = 0; // 만들 수 있는 과자의 개수
    for (int snack : snacks) {
        count += snack / length; // 각 과자를 해당 길이로 나누었을 때 만들 수 있는 개수
        if (count >= m) return true; // 조카의 수 이상이면 가능
    }

    return false; // 조카의 수보다 적으면 불가능
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int m, n; // m: 조카의 수, n: 과자의 수
    cin >> m >> n;

    vector<int> snacks(n);
    for (int i = 0; i < n; i++) {
        cin >> snacks[i];
    }

    // 이분 탐색을 위한 left, right 설정
    int left = 0;
    int right = *max_element(snacks.begin(), snacks.end()); // 가장 긴 과자의 길이
    int result = 0;

    while (left <= right) {
        int mid = (left + right) / 2 // 중간 값 계산

        if (giveSnack(snacks, m, mid)) {
            // mid 길이로 나누는 것이 가능하다면, 더 긴 길이 시도
            result = mid;
            left = mid + 1;
        } else {
            // mid 길이로 나누는 것이 불가능하다면, 더 짧은 길이 시도
            right = mid - 1;
        }
    }

    cout << result << endl;

    return 0;
}