백준 2805번 나무 자르기

Prologue

처음에 후보에 1씩 더하거나 1씩 빼다가 잘 안돼서
어떻게 풀어야할지 생각이 안 나 잠이 들었는데
그 다음날 일어나면서 "이진탐색"하고 소리지르며 일어났습니다. ㅋㅋ

1. 내 코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int array[1000000];

int BSearch(long long left, long long right, int N, int M)
{
	int i;
	long long tree = 0;
	long long mid = (left + right) / 2;

	for (i = 0; i < N; i++)
	{
		if (array[i] > mid) tree += (array[i] - mid);
	}

	if (tree >= M)
	{
		tree = 0;

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

		if (tree < M) return mid;

		else return BSearch(mid + 1, right, N, M);
	}

	else return BSearch(left, mid - 1, N, M);
}

int main()
{
	int i, N, M;
	int max = 0;
	scanf("%d %d", &N, &M);

	for (i = 0; i < N; i++)
	{
		scanf("%d", &array[i]);
		max = max > array[i] ? max : array[i];
	}

	long long left = 1;
	long long right = max;

	printf("%d", BSearch(left, right, N, M));

	return 0;
}

하지만 엄청 빠른 사람은 20ms, 일반적으로도 200ms초반이 걸리는 반면에 나는 260ms가 걸려
그 이유를 찾아보고자 다른 사람들의 코드를 좀 읽어보기로 했다.

2. injoon0617님의 코드 (https://www.acmicpc.net/user/injoon0617)

212ms가 걸린 C언어 전체 7등의 코드이다.
코드도 446바이트인데 지나친 숏코딩 없이 깔끔해보였다.

#include <stdio.h>

int main() {
    int n, m, i, p, q, r, t, a[1000000];
    scanf("%d %d", &n, &m);
    p = q = 0;//p,q는 뭘까?
    for (i = 0; i < n; ++i) {
        scanf("%d", &a[i]);
        if (q < a[i]) q = a[i];//q는 max값이네!
    }
    while (p < q) {
        t = m, r = (p + q) >> 1; -> r은 mid
        //아하 그러면 p는 left, q는 right네!
        for (i = 0; i < n && t > 0; ++i)
            if (a[i] > r) t -= (a[i] - r);
        if (t > 0) q = r;//자르는 나무의 길이의 합이 m보다 크면 left = r
        else p = r + 1;
    }
    printf("%d", p - 1);
    return 0;
}

마지막에 left,right가 같거나 교차하면 left - 1을 출력하는데

이게 어떤 원리인지 이진탐색에서 값을 못 찾을 때를 일반화해보자.

코드에 따르면 left가 right 이상이 되는 순간 left가 가리키는 값은 찾고자 하는 값보다 커야하는데 그렇지 않은 경우가 있는데 어떻게 해야하지?

수정한 나의 코드

f52895님의 코드를 통해
left == right인 순간, 구하고자 하는 값과 mid는 최대 한칸차라는 걸 배웠고 이를 이용하여 시간을 줄여보았다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int array[1000000];

int BSearch(long long left, long long right, int N, int M)
{
	int i;
	long long tree = 0;
	long long mid = (left + right) / 2;

	for (i = 0; i < N; i++)
	{
		if (array[i] > mid) tree += (array[i] - mid);
	}

	if (tree >= M) // tree는 M개 이상 이어야 하고 이 경우는 충분 즉, 이가 최대인지 알아야 한다.
	{
		if (left >= right) //이거 왜 == 하면 안 되지? 한번은 같을 때가 생길텐데?? -> 뒤에서 해결
		{
			tree = 0;

			for (i = 0; i < N; i++)
			{
				tree += (array[i] - (mid + 1));
			}
			
			if (tree < M) return mid;
			else return (mid + 1);
		}
		return BSearch(mid + 1, right, N, M);
	}

	else return BSearch(left, mid - 1, N, M);
}

int main()
{
	int i, N, M;
	int max = 0;
	scanf("%d %d", &N, &M);

	for (i = 0; i < N; i++)
	{
		scanf("%d", &array[i]);
		max = max > array[i] ? max : array[i];
	}

	long long left = 1;
	long long right = max;

	printf("%d", BSearch(left, right, N, M));

	return 0;
}

의문점

(1) if (left >= right)

이 부분을 처음에는 left == right로 했었다.
무조건 한번은 그렇게 되리라 생각했기 때문이다.
그런데 이게 무한루프가 걸린다.
왜지??

이렇게 L과 R이 만나지 않는 경우도 생긴다.

(2) left와 right가 교차하고 tree < M인 경우는 어떡하지?

이러면 바로 찾아야 하는 값으로 가게 되어 조건문 안에서 알맞은 값을 찾게 된다.