2805 나무 자르기

백준 2805번 나무자르기 : https://www.acmicpc.net/problem/2805

2805번: 나무 자르기

이 문제는 이분탐색으로 풀 수 있는 문제다 

이분 탐색 참고 -> https://wh514.tistory.com/20

 

[코드 작성 전]

우선, 높이를 입력받으며 미리 나무 중 가장 높은 높이(hmax)를 저장한다. 

탐색 범위를 0 ~ hmax로 설정하고 이분 탐색을 진행한다. 

• 중간 값(cutter)를 절단기 설정 높이로 가정하고 가져갈 수 있는 나무의 높이를 for문으로 계산한다
• 계산한 값을 M과 대소비교 후 결과에 따라 탐색범위 수정 

 

탐색 후, 나온 값은 M과 가장 가까운 값이므로 M보다 작을 수도 있다. 따라서, 작은 경우에는 따로 처리가 필요하다. 

 

[문제 풀이]

#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, m;
	cin >> n >> m;

	int* tree = new int[n];
	int cutter = 0;
	int hmin = 0;
	int hmax = 0;
	for (int i = 0; i < n; i++) {
		int k;
		cin >> k;
		tree[i] = k;
		hmax = max(hmax, k);
	}

	ll tm = 0;
	while (hmax >= hmin) { // hmax < hmin 이면 탈출
		cutter = (hmin + hmax) / 2;

		tm = 0;
		for (int i = 0; i < n; i++) { // 가져갈 수 있는 나무 높이 계산 
			if (tree[i] > cutter) {
				tm += tree[i] - cutter;
			}
		}
        
		//탐색
		if (m > tm) {
			hmax = cutter - 1;

		}
		else if (m < tm) {
			hmin = cutter + 1;

		}
		else break;
	}

	if (tm < m) cutter--; // 문제의 M보다 작으면 

	cout << cutter;


	return 0;
}

int *tree = new tree	나무 높이를 저장하는 배열
int cutter, hmax, hmin	cutter : 절단기 설정 높이 hmax : 탐색 범위 중 가장 큰 값  - 처음 값은 tree 배열 값 중 가장 큰 값 : 입력 시 설정 hmin : 탐색 범위 중 가장 작은 값
ll tm	탐색중 가져갈 수 있는 나무 값 저장 빛 비교를 위해 사용  - int가 아닌 long long 사용
while(hmax>=hmin)	① 탐색 범위 중간 값 cutter에 저장 ② 현재 cutter값 기준으로 가져갈 수 있는 나무 높이 계산 ③ 현재 가져갈 수 있는 높이와 M과 대소비교 후 hmax,hmin 값 조정 ④ tm == m 또는 hmax < hmin 인 경우 루프 탈출
if(tm<m) cutter--;	가장 가까운 경우이므로, 작으면 cutter--를 통해 값이 커지도록 수정 (다만, 탐색 중 tm이 m보다 큰 경우에만 답을 수정하면 따로 처리가 필요없다.)

 

[comment]

우선 이전에 풀었던 이분탐색을 정리하다가 발견해서 푼거라 이분탐색인걸 알고 시작한게 아쉽다,, 대신 그만큼 빨리 풀긴했다.. 

과거에는 어렵다 생각했었는데 이번에 풀면서 미리 코드를 어떻게 짤지 생각하고 푸니까 쉽게 풀려서 문제풀 때 미리 코드 정리하는 것의 중요성을 깨달아서 좋았다.