백준 2805번 나무 자르기

< 백준 2805번 나무 자르기 - 마포 코딩박 >

사용한 알고리즘: 투포인터, 이분탐색


 N개의 나무의 높이와 원하는 나무길이 M 이 주어진다. 각 나무를 h 의 높이로 잘랐을 때 얻을 수 있는 나무길이는 해당나무높이 - h 이다. N개의 나무에서 얻을 수 있는 나무길이가 M 이상을 만족하는 h 의 최댓값을 구하는 문제이다.

문제풀이는 다음과 같다.
(1) (코드: 15,16)
 lo = 0, hi = Infimum 초기값을 설정 한다.

(2) (코드: 18~29)
 mid=(lo+hi)/2 라고 설정한 뒤, mid 높이로 잘랐을 때 얻을 수 있는 총 나무길이를 sum 이라 하자. 원하는 나무길이 M에 대해
 1. sum>=M 일때 lo = mid 로 높여준다.
 2. sum < M 일때 hi = mid 로 낮춰준다.
 lo + 1 < hi 일때 위 과정을 반복하고, 과정이 끝나면 구해진 lo값이 답이다.

	#include <bits/stdc++.h>
	using namespace std;
	// 이분탐색
	// 가능한 최대 높이
	const int INF = 1e9;
	int N, M, A[1000003], mid;
	long long sum;
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> N >> M;
	for (int i = 0; i < N; ++i) cin >> A[i];
	int lo = 0;
	int hi = INF;
	// 알맞은 높이 찾기
	while(lo+1 < hi){
	mid = (lo+hi)/2;
	sum = 0;
	for (int i =0 ; i < N; ++i)
	if(A[i]>mid)
	sum += A[i] - mid;
	if(sum >= M)
	lo = mid;
	else
	hi = mid;
	}
	cout << lo << '\n';
	return 0;
	}

view raw BOJ 2805.cpp hosted with ❤ by GitHub