BOJ 3487. Copying Books

문제 링크

 

문제 풀이

  이 문제는 $m\leq 500$ 개의 $10^8$ 이하의 숫자와 $k\leq m$ 이 주어질 때 $m$개의 숫자를 $k$개의 집합을 나누어 그 집합들의 합의 최대가 최소가 되도록 하는 문제이다. 이때 같은 집합에 포함되려면 그 수들이 모두 연속해야하며 원소에 개수가 1개 이상이어야한다. 예를 들어 9개의 수 100, 200, 300, 400, 500, 600, 700, 800, 900을 3개의 집합으로 나눈다고 할 때 100,200,300,400,500 / 600,700 / 800,900 으로 나눠야 최대합이 1700으로 최소가 된다. 참고로 나누는 방법이 여러개인 경우는 앞쪽의 집합의 원소의 개수가 가장 작을 때를 출력해야한다.

 

 일단 $m,k$의 범위가 작아서 백트랙킹을 해야하는 줄 알았다. 그런데 가능한 가짓수가 $P(n,k)$ 만큼 이므로 생각을 금방 접었다. 이후에는 이분탐색을 떠올렸는데, 최대합을 기준으로 이분탐색을 하면 최대합의 최소를 찾을 수 있을 것이라고 생각하였다. 또한 숫자의 최댓값을 $N$이라 할때 최대 합의 최소를 구하는 시간복잡도는 $O(logN)$ 밖에 안되므로 아주 넉넉하다. 그래서 매개변수 이분탐색의 방법을 사용하였다.  초기의 $l$은 0, $r$은 모든 숫자들의 합으로 잡아 계산하였다. 이분탐색에서 반환해야하는 값을 헷갈려서 조금 헤맸는데 $l \leq r$ 로 둔 다음에 모든 상황에서의 $mid$를 저장하고  조건을 만족시킬 때 $r = mid - 1$, 만족하지 않을 때는 $l = mid + 1$을 하여 최종적으로는 마지막 $mid$의 값을 출력해주면 됐다.

 

 이런식으로 최대합을 구하면 뒤쪽에서부터 그 합을 넘지않을 때까지 집합으로 분할해주면 되기 때문에 어렵지 않게 구현하였다. 

 

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
typedef long long ll;
const int mmax = 500;

ll m,k;
ll books[mmax+1], sum=0;

void input(){
    cin>>m>>k;
    for(int i=0;i<m;i++){
        cin>>books[i];
        sum += books[i];
    }
}

ll BinarySearch() {
    ll l = 0;
    ll r = sum;      
    ll answer = r;  
    
    while (l <= r) {
        ll mid = (l + r) / 2;
        bool flag = true; 
        
        ll s = books[0], num = 1; 
        for (int i = 1; i < m; i++) {
            if(s > mid || books[i] > mid){
                flag =false;
                break;
            }
            
            if (s + books[i] > mid) {
                num++;
                s = books[i];
                if (num > k) {
                    flag = false;
                    break;
                }
            } else {
                s += books[i];
            }
        }
        
        if (flag) {
            answer = mid;
            r = mid - 1; 
        } else {
            l = mid + 1; 
        }
    }
    
    return answer;
}

void solve(){
    ll mxSum = BinarySearch();
    
    stack<int> st;
    ll s = books[m-1] , num = 1;
    st.push(m-1);
    for(int i=m-2;i>=0;i--){
        if(s + books[i] > mxSum || (i + 1 == k - num)){
            num ++;
            s = books[i];
            st.push(-1);
            st.push(i);
        } else {
            s += books[i];
            st.push(i);
        }
    }
    
    while(!st.empty()){
        int x = st.top();
        st.pop();
        if(x == -1) cout<<"/"<<" ";
        else {
            cout<<books[x]<<" ";
        }
    }
    cout<<"\n";
}

int main(){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    
    int T; cin>>T;
    while(T--){
        sum = 0;
        input();
        solve();
    }
}