백준 16401번 [과자 나눠주기](C++) -yes6686- 티스토리

백준 문제 풀이: 16401 (과자 나눠주기)

---

문제 링크: https://www.acmicpc.net/problem/16401

문제 설명:

과자의 길이가 서로 다를 때, **최대한 길이가 긴 과자**를 만들어 M명의 조카에게 나눠줘야 합니다. 조카에게 나눠줄 수 있는 과자의 길이는 모두 동일해야 하며, 과자를 자를 수 있지만 남는 부분은 버려야 합니다. 이때, 과자의 길이의 **최댓값**을 구하는 문제입니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

int arr[1000001]; // 과자의 길이를 저장하는 배열

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

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

    int maxL = 1; // 과자의 최대 길이 초기값
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        maxL = max(maxL, arr[i]); // 가장 긴 과자의 길이
    }

    int s = 1;      // 최소 길이
    int e = maxL;   // 최대 길이
    int r = 0;      // 결과값 저장

    while (s <= e) {
        int mid = (s + e) / 2; // 과자의 길이 후보 (이진 탐색)

        int cnt = 0; // mid 길이로 나눈 과자 개수 계산
        for (int i = 0; i < n; i++) {
            cnt += arr[i] / mid;
        }

        // 나눈 개수가 조카 수보다 부족하면 길이를 줄여야 함
        if (cnt < m) {
            e = mid - 1;
        }
        // 나눈 개수가 충분하면 길이를 더 늘릴 수 있음
        else {
            s = mid + 1;
            r = mid; // 현재 mid 길이가 가능하므로 결과에 저장
        }
    }

    cout << r; // 최댓값 출력
    return 0;
}

---

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명:

• 이진 탐색 사용: - 과자의 길이의 최댓값을 구하기 위해 **이진 탐색**을 사용합니다. - s는 최소 길이(1), e는 가장 긴 과자의 길이입니다.
• 과자 개수 계산: - 각 과자의 길이를 mid로 나누어 총 몇 개의 과자를 만들 수 있는지 계산합니다.
• 조건 확인 및 갱신: - 나눈 개수 cnt가 조카 수 m보다 작다면, 길이를 줄여야 하므로 e = mid - 1로 조정합니다. - 나눈 개수가 충분하면 길이를 늘려서 더 큰 길이를 확인합니다.

시간 복잡도 분석

• 이진 탐색의 시간 복잡도는 **O(log L)**입니다. 여기서 L은 가장 긴 과자의 길이입니다.
• 각 단계에서 과자의 개수를 계산하는데 걸리는 시간은 **O(n)**입니다.
• 전체 시간 복잡도는 **O(n log L)**입니다.

---

결과

조카에게 나눠줄 수 있는 과자의 길이의 최댓값을 출력합니다.

• 입력 예시:

  3 10  
  1 2 3 4 5 6 7 8 9 10

• 출력 예시:

  3

추가 설명:

• 이진 탐색을 사용하여 최적의 해를 빠르게 찾을 수 있습니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!