ray

ray

매일의 HIGHLIGHT를 찾아서 ✨

[백준] 2512 예산 (C++)

Posted on Feb 17, 2021 #이진 탐색(Binary Search)   #Algorithm   #C/C++  

2512 | 예산

🙋‍♀️ 문제

국가의 역할 중 하나는 여러 지방의 예산요청을 심사하여 국가의 예산을 분배하는 것이다. 국가예산의 총액은 미리 정해져 있어서 모든 예산요청을 배정해 주기는 어려울 수도 있다. 그래서 정해진 총액 이하에서 가능한 한 최대의 총 예산을 다음과 같은 방법으로 배정한다.

  1. 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정한다.
  2. 모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산요청에는 모두 상한액을 배정한다. 상한액 이하의 예산요청에 대해서는 요청한 금액을 그대로 배정한다.

예를 들어, 전체 국가예산이 485이고 4개 지방의 예산요청이 각각 120, 110, 140, 150이라고 하자. 이 경우, 상한액을 127로 잡으면, 위의 요청들에 대해서 각각 120, 110, 127, 127을 배정하고 그 합이 484로 가능한 최대가 된다.

여러 지방의 예산요청과 국가예산의 총액이 주어졌을 때, 위의 조건을 모두 만족하도록 예산을 배정하는 프로그램을 작성하시오.

🙌 입출력

첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 100,000 이하이다. 그 다음 줄에는 총 예산을 나타내는 정수 M이 주어진다. M은 N 이상 1,000,000,000 이하이다.

첫째 줄에는 배정된 예산들 중 최댓값인 정수를 출력한다.

🙋‍♂️ 예제 입출력

4
120 110 140 150
485

127

예산 / 지방의 수를 평균으로 잡고 문제를 풀었을 때 틀리는 출력예시

4
1 5 6 100
18

6

🚀 코드

#include <iostream>
#include <cstdlib>
#include <vector>
#include <algorithm>
using namespace std;

int n = 0;
long m = 0; // 10^6을 넘어감
vector<int> v;
long sum = 0; // 얘도 long으로 잡아줌

void findCost() {
	// 1 5 6 100 예산 18인 경우처럼
	// 내 방법은 예산을 기준으로 탐색하니까 빠르긴한데
	// 커버 못치는 부분이 존재.
	// m을 가지고 이분탐색을 하며 구해야 정확하게 구할 수 있음

	int lo = 0;
	int hi = m;
	int mid = 0;
	int rst = 0;
	long long sum = 0;
	while (lo <= hi) {
		mid = (lo + hi) / 2;
		sum = 0;
		// mid값을 기준으로 총 예산을 계산해봄
		for (int i = 0; i < n; i++) {
			if (v[i] <= mid) {
				sum += v[i];
			}
			else sum += mid;
		}

		if (sum <= m) {
			rst = mid;
			lo = mid + 1;
		}
		else {
			hi = mid - 1;
		}
	}

	cout << rst;
	return;
}

int main() {
	cin >> n;
	int x = 0;
for (int i = 0; i < n; i++) {
		scanf("%d", &x);
		v.push_back(x);
		sum += x;
	}
	cin >> m;
	sort(v.begin(), v.end());
	if (sum <= m) {
		// 정렬한 뒤이므로 맨 뒤의 원소가 최댓값
		printf("%d", v.back());
	}
	else {
		// 계산된 정수 상한액이 최댓값임
		findCost();
	}
	return 0;
}

🌠 메모

칭찬할 점!!
이번엔 문제 보고 한번에 자료형까지 잘 생각해서 선언했다.(m, sum을 long long으로)

이 문제는 이해하는데 시간이 좀 걸린 문제였는데, 어떻게 풀어야 할 지 감이 잘 안왔다. 문제 분류가 이진탐색이어서 이진 탐색을 써야겠구나 싶긴 했는데, 만약 그 사실을 몰랐다면 한참 헤맸을 것 같다.

삽질 기록..

처음에는 예산 총액을 지방의 수로 나눈 평균 avg을 가지고 예산들을 저장한 배열 v에서 이진 탐색을 했다.

그 뒤에 avg보다 작거나 같은경우 거기서 발생하는 마진(avg가 12이고 4, 6인 예산이 존재한다면 각각 8, 6만큼 마진 발생)을 모두 더하고 avg보다 큰 예산에게 골고루 나눠준다.

따라서 예산은 avg + (마진 / avg보다 큰 예산의 개수)가 된다. 이 경우, 예제 입출력을 포함해 어드정도는 커버가 가능한데 틀린 코드였다…

두 번째 입출력의 경우 내 코드로 하면 답이 4가 나오고 이 경우 예산은 총 13으로 18보다 작지만, 예산을 6으로 잡으면 딱 18만큼 사용할 수 있다.

✨ 수정된 방법

고친 방법으로는 avg, 마진 등을 생각하지 않고, 단순하게 0부터 m까지 이진탐색을 진행하고, 각 경우 나오는 mid값을 가지고 실제 예산액을 계산해준다. (mid보다 작으면 그대로 더하고, 크면 mid 더하기) 계산된 결과값을 m과 비교하며 탐색을 진행하도록 한다.



# 카테고리