Post

[BOJ] 14627 - 파닭파닭

문제 링크

나는 분명 이분탐색에 대해 이제 어느정도 이해를 하고 있다고 생각했는데,, 아닌 것 같다.
처음에는 L과 R을 mid로만 옮겨주었는데, 그렇게 했을 때는 틀렸습니다가 나왔고 mid를 제외한 범위에서 탐색했을 경우에 정답처리가 되었다.
왜 이렇게 풀면 틀리는지 확실히는 알지 못한다.. 나중에 이유를 알게 되면 추가하도록 하자.

소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#include <algorithm>
#include <limits.h>
#define MAX 1000000000
using namespace std;
typedef long long ll;

ll len[1000005];
ll all;

int main(void) {
    int s, c;
    scanf("%d %d", &s, &c);
    for (int i = 0; i < s; i++) {
        scanf("%lld", len + i);
        all += len[i];
    }
    ll L = 1, R = MAX + 1, ans = LLONG_MAX - 1;
    while (L <= R) {
        ll mid = (L + R) / 2, cnt = 0;
        for (ll now : len) {
            cnt += now / mid;
            if (cnt >= c) {
                ans = min(ans, all - mid * c);
                break;
            }
        }
        if (L == mid) {
            cnt = 0;
            for (ll now : len) {
                cnt += now / R;
                if (cnt >= c) {
                    ans = min(ans, all - R * c);
                    break;
                }
            }
            break;
        }
        if (cnt < c) R = mid - 1;
        else L = mid + 1;
    }
    printf("%lld", ans);
    return 0;
}
This post is licensed under CC BY 4.0 by the author.

Comments powered by Disqus.