CS/알고리즘 문제 풀이
[백준] 2805 - 나무 자르기 [Python(파이썬)]
문제 www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 풀이 이진탐색 문제였다. N의 범위가 크기 때문에 O(N^2)의 풀이로는 시간초과가 날 수 밖에 없다. 절단한 나무 길이의 합(_sum)을 집으로 가져가야 하는 나무의 길이(M)와 비교하여 포인터를 옮긴다. 이때, 합이 길이보다 작다면 right포인터를 mid-1로 줄여서 탐색의 범위를 줄인다. 반대로 크다면 left포인터를 mid+1로 옮긴 후, 현재 mid포인터가..
