[백준]통나무 자르기(1114)

문제 링크 : [백준]통나무 자르기(1114)

문제 설명

길이 L의 통나무가 주어지고, 통나무를 자를 수 있는 위치가 K개 주어집니다.
그 위치 중 C번만 나무를 자르는 경우중에서 가장 긴 나무의 길이가 가장 작게 했을 때, 가장 긴 나무의 길이와 가장 처음 자르게 되는 위치를 구하세요.(자를 수 있는 처음 위치가 여러가지인 경우, 제일 먼저 자르는 것을 출력하세요.)

입력

L(통나무의 길이, 1 <= L <= 1,000,000,000)
K(통나무를 자를 수 있는 위치의 갯수, 1 <= K <= 10,000)
C(최대로 자를 수 있는 횟수, 1 <= C <= 10,000)
P_i(통나무를 자를 수 있는 위치(통나무의 제일 왼쪽 기준))

9 2 1
4 5

출력

5 4

카테고리

#이분탐색 #그리디

시간 복잡도 상한

O(K²), O(C²), O(K * c)

해결 방법

1. DP로 접근하려고 하였으나, 10,000 * 10,000의 메모리가 필요 할 것 같아 접었습니다.
2. 특정 길이 이내로 자를 수 있는지를 파악하는 것은 어렵지 않을 것 같습니다.
   2-1. 기준 길이를 정하고, 인덱스를 순차적으로 순회하면서 누적합을 구하며, 기준 길이보다 길어지게 되면 그 위치에서 자르고 다시 누적합을 구하는 식으로 하면 됩니다.
   2-2. 자르는 횟수가 C보다 작거나 같으면 기준 길이 이하로 가장 긴 통나무를 만들 수 있습니다.
3. 그러나 그렇게 되면 특정 길이에서 K번의 시간복잡도가 발생하며, 기준길이 모두를 탐색하게 되면, 10억 * K의 시간복잡도가 생겨서 TLE가 됩니다.
4. 그런데 특정 길이에서 성공을 하였다면, 우리는 그것보다 긴 길이를 확인할 필요가 없습니다.
5. 이미 특정 길이에서 성공하였는데, 우리는 성공할 수 있는 최소길이를 구하는 것이기 때문에 그것보다 큰 값은 궁금하지 않습니다.
6. 반대로, 특정길이에서 실패하였다면, 그 길이보다 작은 길이는 어차피 실패할 것이므로 확인할 필요가 없습니다.
7. 즉 특정 길이를 이분탐색으로 하면서 구하면 빠르게 답을 구할 수 있습니다.
8. 단, 자르는 위치가 순서대로 주어지는 것이 아니기 때문에 입력 받은 위치를 정렬해야 합니다.
9. 그리고 특정 길이보다 긴 나무 토막이 존재한다면 그 길이는 무조건 실패하는 것으로 처리해야 합니다.
10. 그렇다면 제일 먼저 자르는 위치는 어떻게 구할까요??
11. 2에서 특정길이 이상의 누적합이 발생하였을 때, 자르는 위치를 뒤에서부터 탐색한다면, 자르는 위치는 최대한 앞으로 당겨지면서 구해질 것입니다.
12. 따라서 뒤에서 잘라오면서 구하면 마지막으로 자르는 곳이 그 위치가 될 것입니다.
13. 단, 자른 횟수가 C보다 작다면 무조건 맨 앞에서 한번 더 자를 수 있으므로, 맨 앞이 답이 됩니다.

시간복잡도

O(KlogL)

코드

#include<cstdio>
#include<algorithm>
#define N 1000000000
int n,m,k,d[10001],e[10001],i,a,b,c,s,l,r=N,x,p;
int main(){
    scanf("%d%d%d",&n,&m,&k);
    for(i=0;i<m;i++)scanf("%d",d+i);
    d[m]=n;
    std::sort(d,d+m);
    e[0]=d[0];
    for(i=1;i<=m;i++)e[i]=d[i]-d[i-1];
    while(l<=r){
        x=(l+r)/2;
        for(p=s=c=0,i=m;i>=0;i--){
            if(e[i]>x){
                c=k+1;
                break;
            }
            if(s+e[i]>x){
                s=0,c++;
                p=i;
            }
            s+=e[i];
        }
        if(c>k)l=x+1;
        else {
            a=x;r=x-1;
            b=c==k?d[p]:d[0];
        }
    }
    printf("%d %d",a,b);
}