백준2805 나무 자르기

작성일 | In

문제 링크

  • http://icpc.me/2805

문제 출처

  • 2011/2012 COCI Contest #5 2번
  • 2018 IOI 여름학교 3일차 2번
  • 2018 이데일리 코딩 챌린지 예선 문제(떡볶이 자르기)

사용 알고리즘

  • Parametric Search

시간복잡도

  • O(N log N)

풀이

이 문제는 parametric search를 이용하여 푸는 문제입니다. 나무의 높이를 정렬한 후, value미터에서 잘랐을 때 몇 미터를 가져갈 수 있는지를 O(log n)만에 계산하는 함수를 만든 뒤, 그 함수를 이용해 parametric search를 이용해 정답을 찾으면 됩니다.

풀이 방법은 다음과 같습니다.

  1. 입력 받은 나무의 높이를 정렬합니다. O(N log N)
  2. 정렬된 나무들의 총 합과 누적 합을 구합니다. O(N)
  3. 총 합과 M이 같으면 0을 출력하고 프로그램을 종료합니다.
  4. 모든 나무에 대해 해당 나무의 높이에서 잘랐을 때의 결과가 M과 같은 지 비교한 뒤, 같다면 해당 나무의 높이를 출력하고 프로그램을 종료합니다. O(N)
  5. 3, 4번 조건에 해당하지 않는다면, parametric search를 수행해서 결과를 출력합니다. O(log N) 최종 시간 복잡도: O(N log N)

전체 코드

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int arr[1000010];
ll nu[1000010];
ll n, m, sum = 0;

ll conv(int value){
	int* it = upper_bound(arr, arr+n, value);
	int idx = it-arr;
	ll ret = sum - ( (ll)value*(n-idx) + nu[idx-1] );
	return ret;
}

int search(){
	int l = 1e9, r = 0;
	int mid;
	while(1){
		mid = (l+r)/2;
		ll c = conv(mid);
		if(l < r){
			return l;
		}
		if(c <= 0){
			l = mid-1;
			continue;
		}
		if(conv(mid+1)<m && c>m){
			return mid;
		}
		if(m > c){
			l = mid-1;
		}
		else r = mid+1;
	}
}