[Jungol] 정올 1156 책 복사하기2

출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=436&sca=40

 

Approach

Binary Search (이분 탐색) 

Binary Search (이분 탐색)

[탐색] Parametric Search 

[탐색] Parametric Search

- 서기공과 책의 수가 최대 100,000개 이므로 순차탐색으로는 TLE 발생 → 이분탐색

- 출력형식에 있어서 앞선 서기공이 할 일이 가장 적게해야 하므로 반대로

   → 뒤에서부터 가능한 범위 내에서 최대한 많은 책을 배정 (책 리스트를 출력할 때, 『 / 』로 구분)

Parametric Search 이용 → 가장 많은 페이지를 맡은 서기공의 페이지 수를 이분탐색 과정으로 찾아갑니다.

- 한 명의 서기공이 적어도 책 한 개는 맡아야 하므로 page의 최소값을 low로 설정

- 한 명의 서기공이 모든 책을 맡는다고 가정했을 때, 모든 page의 합을 high로 설정

ex) 2000 Page를 K개의 구간으로 구분할 수 있다.

    O : 2000page 보다 작은 기준(mid)으로 재탐색

    X : 2000page 보다 큰 기준(mid)으로 재탐색

---

page의 크기가 작지 않으므로 typedef long long ll; 사용

#include <stdio.h>
typedef long long ll;
const int LM = 100005;
 
int N, K, arr[LM];
ll low, high, ans;
 
void input() {
    scanf("%d %d", &N, &K);
    for (int i = 0; i < N; ++i) {
        scanf("%d", arr + i);
        if (low < arr[i]) low = arr[i];
        high += arr[i];
    }
}
 
int check(ll mid) {
    int i, groupCnt = 1;
    ll sum = 0;
    for (i = 0; i < N; ++i) {
        if (sum + arr[i] > mid) {
            groupCnt++;
            sum = arr[i];
        }
        else {
            sum += arr[i];
        }
    }
    return groupCnt <= K;
}
 
void output(int idx, ll sum, int ck) {
    // printf("%lld\n", ans);
    if (idx < 0) return;
    if (sum + arr[idx] > low || idx < ck) {
        output(idx - 1, arr[idx], ck - 1);
        printf("%d / ", arr[idx]);
    }
    else {
        output(idx - 1, sum + arr[idx], ck);
        printf("%d ", arr[idx]);
    }
}
 
void process() {
    while (low <= high) {
        ll mid = (low + high) / 2;
        if (check(mid)) {
            ans = mid;
            high = mid - 1;
        }
        else {
            low = mid + 1;
        }
    }
}
 
int main() {
    // freopen("input.txt", "r", stdin);
    input();
    process();
    output(N - 1, 0, K - 1);
    return 0;
}