개요

백준 2512번: 예산

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

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

접근 방식

직전에 푼 백준 2805(나무 자르기) 문제와 유사하다.

나무자르기 문제에선 가져가려는 나무의 길이가 1보다 크기 때문에
high값을 해당범위의 가장 끝값으로 설정했어도 문제가 없었는데

이 문제는 해당 범위의 끝값이 low값이 되고 high값은 범위를 벗어나는 값이 될 수 있으므로
high값을 최대한 크게 설정해야한다.

코드

#include<iostream>
#include<algorithm>

using namespace std;
//총 갯수, 국가총예산
int N,target;
//동적계획법이 아닌데도 그냥 dp가 익숙해서 이름을 이따구로 지음
int dp[10'001];

//입력받는 함수
void input() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> dp[i];
	}
	sort(dp, dp + N);
	cin >> target;
}

//값이 middle값보다 크면 middle값 더하고 작다면 해당 값 더해서 총합 return하는 함수
int cut(int middle) {
	int sum = 0;
	for (int i = 0; i < N; i++) {
		if (dp[i] >= middle) {
			sum += middle;
		}
		else {
			sum += dp[i];
		}
	}
	return sum;
}

void solution() {
	//low = 0, high = dp[N-1] 이런식으로 high값을 해당범위의 끝으로 잡으면 해당범위 끝이 답일때 그답-1이 답으로나옴
	int low = 0, high = 100'001,mid=0;
	//이렇게 구현하면 high가 엄청 큰값이 들어가도 cut에선 dp배열에 들어온 값들을 다 더해버리기만하므로 
	//high값이 그대로 답으로 나옴 
	while (low + 1 < high ) 
	{
		//따라서 범위의 끝값을 넣어도 조건을 만족한다면 끝값 출력하고 끝
		if (cut(dp[N - 1]) <= target) {
			cout << dp[N - 1];
			return;
		}
		mid = (low + high) / 2;
		if (cut(mid) <= target) 
			low = mid;
		else
			high = mid;
		
	}
	cout << low;
}

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

문풀후생

첨에 국가총예산을 고려안하고 대충 풀었더니
high를 10만으로 설정하면 10만이 답으로 나와서 좀 고민하고 문제를 다시 읽었다.

처음 볼 때 꼼꼼히!