BOJ 백준 [2805] 나무 자르기

IDEA N의 최댓값은 1,000,000이며 M의 최댓값은 2,000,000,000이다. 가능한 모든 높이의 길이를 탐색하여 답을 구하고자 한다면, 1,000,000 * 2,000,000,000 즉, 주어진 시간제한을 넘길 것이다. 이를 해결하기 위해서 좀 더 생각을 해보자. 나무가 나열된 순서는 상관이 없다. 그렇다면 나무를 순서내로 나열 시켜보자. 위와 같이 나무를 정렬 시켰을 때, 자르고자 하는 나무의 높이를 이분탐색하여 찾는다고 생각해보자. 우선, 나무를 정렬시키는데 사용되는 시간은 NlogN --> 1,000,000*lg1,000,000 약, 20,000,000의 시간이 소요된다. 그리고 이분탐색을 이용하여 높이의 최댓 값을 탐색해보자. NlogM --> 1,000,000*lg2,000,000,..

2019.09.04