개요

백준 2805: 나무 자르기

• 입력
  첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000)

  둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보다 크거나 같기 때문에, 상근이는 집에 필요한 나무를 항상 가져갈 수 있다. 높이는 1,000,000,000보다 작거나 같은 양의 정수 또는 0이다.

• 출력
  적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 출력한다.

접근 방식

자를 값을 범위의 반으로 설정 후,
해당 값으로 잘랐을 때 가져가게 될 길이가 타겟 길이보다 작다면
범위를 변경하는 방식의 이분탐색 방식을 떠올렸다.

하지만 구현하는 과정에서 이렇게 구현했다.

	long long mid = 0;
	while (low <= high) {
		mid = (low + high) / 2;
		if (cut(mid) >= M) low = mid + 1;
		else high = mid - 1;
	}
	cout << mid;

어렴풋이 예전에 풀었던 과정으로 풀어봤으나 제대로 이해를 못하고 풀이만 떠올려서 그런지
바로 mid를 출력하게 했고 틀렸다.
고쳐보자면 low값은 cut(mid)=M 단계에서 mid+1값이 되니 low는 답이 안되고,
다음 단계에선 cut(mid)<M이 되니 high가 mid-1이 실행 되어 high값이 답이 된다.

따라서 cout<<mid; 가 아니라
cout<<high ;나 cout<<(low+high)/2; 를 이용해 답을 출력해야한다.

• 두번째 방법으론

low를 조건에 만족하는 최댓값으로 설정하고 high를 불만족하는 최솟값으로 설정해서
접근하게 되면 low와 high값을 다 mid값을 넣어 주고
비교문을 low+1<high 이렇게 작성하면 답이 나온다.

코드

#include<iostream>
#include<algorithm>

using namespace std;
//나무의 수, 가져가려하는 타겟 길이
int N, M;
//들어오는 나무 길이
int inputArr[1'000'000];

void input() {
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		cin >> inputArr[i];
	}
	//들어온값 정렬
	sort(inputArr, inputArr + N);
}

//middle길이로 잘랐을때 얼마나 가져갈수있는지 
long long cut(long long middle) {
	long long  sum = 0;
	for (int i = 0; i < N; i++) {
		if(inputArr[i] - middle>=0)
			sum += inputArr[i] - middle;
	}
	return sum;
}

//이분탐색 코드
void solution() {
	//조건을 만족하는 최대값 low, 조건을 불만족하는 최소값 high로 설정
	long long low = 0, high = inputArr[N-1];
	//low와 high가 1차이 날 때까지
	while (low+1 < high) {
		//mid값은 low와 high더한값이 int값 넘어갈 수도 있으므로 long long으로 선언
		long long mid = (low + high) / 2;

		//mid값으로 잘랐을 때 타깃 길이인 M보다 같거나 크다면 low값을 mid로 변경해줌
		if (cut(mid) >= M) low = mid;
		//작다면 high값을 mid로 변경해주어 범위를 바꿔준다.
		else
			high = mid;
	}
	//답을 만족하는 최대값인 low을 출력
	cout << low;

}

int main() {
	input();
	solution();
}

문풀후생

범위가 커서 mid값 계산할 때 low high더하는 과정에서 스택 오버플로 일어날 수 있다!!
long long 사용하자
오랜만에 풀었더니 low high설정을 이상하게 했고,
이를 통해 내가 이 부분을 예전에 확실히 공불안해서 모른다는걸 알게되었다.
몇 문제 더풀어보며 공부하자