[BOJ 1114] 통나무 자르기

https://www.acmicpc.net/problem/1114

1114번: 통나무 자르기

 

- 문제 요약

 

벌목꾼 백은진은 나무를 종이 공장에 옮겨야 한다. 하지만, 통나무의 길이가 너무 길어서 트럭에 들어가지 않으므로, 여러 개의 조각으로 나누려고 한다.

통나무의 길이는 L이고, K개의 위치에서만 자를 수 있다. 통나무를 자를 수 있는 위치가 주어진다. 이 위치는 통나무의 가장 왼쪽에서부터 떨어진 거리이다. 통나무를 자를 수 있는 횟수는 최대 C번이다.

통나무의 가장 긴 조각을 작게 만들고, 그 길이를 구해보자.

 

 

- 알고리즘 정리

 

전체 통나무의 길이가 L이라고 했으니, 단순히 오른쪽부터 시작해서 목표 길이에 가장 가깝게 잘라주면 됩니다.

 

 

- 코드 작성

 

#include<bits/stdc++.h>
using namespace std;

#define MAX 10001
int l,k,c,arr[MAX];

int f(int w){
    int tmp=0,from=l,cc=c;
    for(int i=k-1;i>=0&&cc>0;i--){ 
        if(from-arr[i]>w){
            if(arr[i+1]-arr[i]>w){
                return -1;
            }
            cc--;
            from=arr[i+1];
        }
    }
    if(cc>0){
        from=arr[0];
    }

    if(from>w){
        return -1;
    }
    else{
        return from;
    }
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>l>>k>>c;
	for(int i=0;i<k;i++){
		cin>>arr[i];
	}
	sort(arr,arr+k);
	arr[k]=-1;
	int w=0,start=l/(c+1),end=l,mid,result;
	for(int i=0;i<k;i++){
        arr[w]=arr[i];
        if(arr[i]!=arr[i+1]){
        	w++;
		}
	}
	k=w;
	arr[k]=l;
	while(start<end){
        mid=(start+end)/2;
        result=f(mid);
        if(result>=1){
        	end=mid;
		}
		else{
			start=mid+1;
		}
	}
	cout<<start<<" "<<f(start)<<'\n';
}

코드 제출 결과