백준(baekjoon) [C] - 2512번: 예산

https://www.acmicpc.net/problem/2512

2512번: 예산

---

#include <stdio.h>  // 예산

int binary_search(int low, int high, int*arr, int n, int m)
{
	int sum;
	int mid = (low + high) / 2;
	while (high >= low)
	{
		sum = 0;
		mid = (high + low) / 2;
		for (int i = 0; i < n; i++)
		{
			if (arr[i] > mid)
			{
				sum += mid;
			}
			else
			{
				sum += arr[i];
			}
		}
		if (sum == m)
		{
			return mid;
		}
		else if (sum > m)
		{
			high = mid - 1;
		}
		else
		{
			low = mid + 1;
		}
		mid = (low + high) / 2;
	}
	return mid;
}


int main()
{
	int n;
	scanf("%d", &n);

	int arr[10000], max = 0;
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &arr[i]);
		if (arr[i] > max)
			max = arr[i];
	}

	int m;
	scanf("%d", &m);

	printf("%d", binary_search(0, max, arr, n, m));

	return 0;
}

---

MEMO

-- 일반적인 인덱스의 값을 left, right로 설정해서 수를 찾아내는 경우와는 다르게 실제 값을 사용해서 이진탐색을 구현하는 경우가 새로운 느낌

-- 변수 mid == 상한액으로 생각하면 쉽게 이해가 된다

 

!! 더 다양한 문제 풀어보기 !!