BOJ 13702번: 이상한 술집

문제

---

문제 풀이1 - 맞왜틀?

최대: 용량 중 최댓값
1. 나눈 총합이 친구들의 수보다 작으면 용량을 줄이고
2. 크거나 같으면 답을 갱신시킨 후 크면 용량을 증가시킨다.

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

int arr[10001];
int n, k, ans;

void binary_search(int start, int end) {
    if (start > end) { return; }
    int cnt = 0, mid = (start + end) / 2;

    for (int i = 0; i < n; i++) { cnt += arr[i] / mid; } // 나눈 총합

    if (cnt < k) { return binary_search(start, mid - 1); }
    else {
        ans = mid;
        if (cnt > k) { return binary_search(mid + 1, end); }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int num = 0;
    cin >> n >> k;

    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        num = max(num, arr[i]);
    }

    binary_search(1, num);

    cout << ans;

    return 0;
}

대체? 맞왜틀?

질문게시판에서 이유를 찾을 수 있었다.

---

문제 풀이2 - 맞았습니다!

막걸리의 용량은 2^31 -1 보다 작거나 같은 자연수 또는 0이다.
>> int형 범위 안에 들지만 이분탐색 과정에서 변수에 오버플로가 발생할 수 있다.

그래서 오버플로가 발생할 수 있는 변수들을 long long 으로 바꿔줬다.

또한, 1차 풀이처럼 친구들의 수와 나눈 총합이 같다고 이분탐색을 종료시키면 아래의 입력에서는 처음 mid 값인 38을 출력하게 된다. (나눈 총합과 친구들의 수가 일치하므로)

1 1
50

총합이 맞아도 그 중에서의 최대값을 찾아야하니 이분탐색을 끝까지 진행해야한다.

1. 나눈 총합이 친구들의 수보다 작으면 용량을 줄이고
2. 크거나 같으면 답을 갱신시키고 용량을 증가시킨다.

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

int arr[10001];
int n, k;
long long ans;

void binary_search(long long start, long long end) {
    if (start > end) { return; }
    int cnt = 0;
    long long mid = (start + end) / 2;
    cout << "***mid: " << mid << '\n';


    for (int i = 0; i < n; i++) { cnt += arr[i] / mid; } // 나눈 총합

    cout << "***cnt: " << cnt << '\n';
    if (cnt < k) { return binary_search(start, mid - 1); }
    else {
        ans = mid;
        return binary_search(mid + 1, end);
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int num = 0;
    cin >> n >> k;

    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        num = max(num, arr[i]); // 최댓값
    }
    cout << "***num: " << num << '\n';


    binary_search(1, num);

    cout << ans;

    return 0;
}

---

좀 잘 좀 보고 내지... 테스트 용으로 중간 과정 변수들을 cout했던 코드를 안 지우고 제출해서 오답 기록을 많이 남겼다 ㅋㅋㅋㅋㅋㅋㅋ ㅜ