[BaekJoon 16401번] 과자 나눠주기(C++)

※주의※

저의 풀이가 정답은 아닙니다.

다른 코드가 더 효율적이거나 좋을 수 있습니다.

언제나 다른 사람의 코드는 참고만 하시기 바랍니다.

 

 

[문제 풀이 사이트]

 

 

16401번: 과자 나눠주기

 

 

[문제 설명]

 

 

명절이 되면, 홍익이 집에는 조카들이 놀러 온다. 떼를 쓰는 조카들을 달래기 위해 홍익이는 막대 과자를 하나씩 나눠준다.

조카들이 과자를 먹는 동안은 떼를 쓰지 않기 때문에, 홍익이는 조카들에게 최대한 긴 과자를 나눠주려고 한다.

그런데 나눠준 과자의 길이가 하나라도 다르면 조카끼리 싸움이 일어난다. 따라서 반드시 모든 조카에게 같은 길이의 막대 과자를 나눠주어야 한다.

M명의 조카가 있고 N개의 과자가 있을 때, 조카 1명에게 줄 수 있는 막대 과자의 최대 길이를 구하라.

단, 막대 과자는 길이와 상관없이 여러 조각으로 나눠질 수 있지만, 과자를 하나로 합칠 수는 없다. 단, 막대 과자의 길이는 양의 정수여야 한다.

 

 

[입력]

 

 

첫째 줄에 조카의 수 M (1 ≤ M ≤ 1,000,000), 과자의 수 N (1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에 과자 N개의 길이 L1, L2, ..., LN이 공백으로 구분되어 주어진다. 과자의 길이는 (1 ≤ L1, L2, ..., LN ≤ 1,000,000,000) 를 만족한다.

 

 

[출력]

 

 

첫째 줄에 조카 1명에게 줄 수 있는 막대 과자의 최대 길이를 출력한다.

단, 모든 조카에게 같은 길이의 막대과자를 나눠줄 수 없다면, 0을 출력한다.

 

 

[입출력 예]

 

 

입력	출력
3 10 1 2 3 4 5 6 7 8 9 10	8
4 3 10 10 15	7

 

 

[문제 풀이]

 

 

이분 탐색을 이용하여 풀 수 있는 문제이다.

 

1. N개의 과자들을 배열에 저장하고 오름 차순 정렬한다.

 

2. 초기 start 변수는 과자의 길이가 가장 작은 값 1, end 변수는 과자의 길이가 가장 큰 값으로 둔다.

 

3. M명의 조카들에게 나눠줄 막대 과자의 최대 길이를 구해야 한다.

mid 변수인  (start + end) / 2 만큼 나눠줄 때 몇 명(result 변수)에게 나눠줄 수 있는지 구한다.

 

3-1. 구한 갯수(result 변수)가 M명의 조카보다 작다면

과자 길이가 길어서 나눠줄 수 없기 때문에 end 변수를 mid - 1로 변경한다.

 

3-2. 구한 갯수(result 변수)가 M명의 조카보다 크거나 같다면

다 나눠줄 수 있는 과자 길이이므로 start 변수를 mid + 1로 변경한다.

추가적으로 최대 길이를 저장할 변수(maxLen)에 나눠줄 수 있는 과자 길이(mid 변수)를 저장한다.

 

 

이분 탐색에 관한 개념은 아래에 자세히 설명되어 있다.

[Algorithm] 이분 탐색(Binary Search)

 

 

[최종 코드]

 

 

[GitHub]

 

 

GitHub - SmallPeanutPark/BAEKJOON: Study BaekJoon for Coding Test

 

 

#include <bits/stdc++.h>
using namespace std;
vector<long long> snack;

void input(int N) {
    for (int i = 0; i < N; ++i) {
        long long n; cin >> n;
        snack.emplace_back(n);
    }
}

long long cal(long long num) {
    long long ans = 0;
    for (long long element : snack) {
        ans += (element / num);
    }
    return ans;
}

long long binarysearch(int M) {
    long long start = 1;
    long long end = snack[snack.size() - 1];
    long long maxLen = 0;
    while (start <= end) {
        long long mid = (start + end) / 2;
        long long result = cal(mid);
        if (result >= M) {
            maxLen = max(maxLen, mid);
            start = mid + 1;
        }
        else {
            end = mid - 1;
        }
    }
    return maxLen;
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int M, N; cin >> M >> N; // 조카의 수, 과자의 수
    input(N);
    sort(snack.begin(), snack.end()); // 오름 차순 정렬
    long long answer = binarysearch(M);
    cout << answer;
    return 0;
}