[백준 2805] 나무자르기

기억하자.

 

어떤 직선에서 특정값을 찾아야 한다 => 이분탐색 문제! logN

 

나무를 자르는 행위는 시간복잡도가 N이다

 

고로 이문제는 이분탐색 + 나무자르기로 NlogN에 풀 수 있다!

 

 

 

 

이분탐색 하는법

• left와 right 값을 설정한다
• mid값 기준으로 while(left <= right) 일 때 알고리즘을 수행한다
• 값을 찾지 못하면 left에는 mid+1 값을 주거나 right에 mid -1 값을 주면서 계속 찾는다

 

 

c++

#include<iostream>


using namespace std;

int tree[1000001];
int N, M;
int main() {
	cin >> N >> M;
	int left = 1;
	int right = 0;
	for (int i = 1; i <= N; i++) {
		cin>>tree[i];
		right = right > tree[i] ? right : tree[i];
	}
	long long ans = 0;
	while (left<=right)
	{
		long long sum = 0;
		int mid = (left + right) / 2;

		for (int i = 1; i <= N; i++) {
			if (tree[i] > mid)sum += tree[i] - mid;
		}

		if (sum >= M) {
			left = mid + 1;
			ans = ans > mid ? ans : mid;
		}
		else {
			right = mid - 1;
		}

		
	}
	cout << ans << endl;


	return 0;
}

 

 

파이썬

import sys
N, M = map(int,sys.stdin.readline().split())

wood = list(map(int,sys.stdin.readline().split()))
wood.sort(reverse=True)

left  = 1
right = wood[0]
ans = 0
while(left <= right):
    mid = int((left + right) / 2)
    sum = 0
    for i in wood:
        if i > mid:
            sum += i - mid
        else:
            break

    if sum >= M:
        left = mid + 1
        ans = ans if ans > mid else mid
    elif sum < M:
        right = mid -1


print(ans)