💉문제 내용

문제 풀러가기

💉입출력

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

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

🔋예제 입출력

🔮예제 입력1

4
120 110 140 150
485

🔮예제 출력1

127

🔮예제 입력2

5
70 80 30 40 100
450

🔮예제 출력2

100

💉문제 분석

🔋분류

이분탐색

🔋난이도

실버III

💉문제 풀이

🔋해법

전형적인 이분탐색문제입니다.
만약 조건에 맞는다면 결과값의 최댓값을 계산한뒤 값을 늘리고,
맞지않는다면 값을 줄였습니다.

조건은 다음과 같습니다.

1. 먼저 값이 저장된 배열의 값을 순회하면서 다음 조건분기에 맞게 count의 값을 계산합니다.
   > mid의 값보다 크다면 mid의 값을 넣는다.
   > mid의 값보다 작거나같다면 그때의 배열의 값을 넣는다.
2. count의 값이 M보다 작거나 같다면 참, 아니라면 거짓

🔋소스코드

#include <bits/stdc++.h>

std::vector<int> arr;

bool possible(int M, int x) {
	int count = 0;

	for (int i = 0; i < arr.size(); ++i) {
		if (arr[i] > x) count += x;
		else if (arr[i] <= x) count += arr[i];
	}

	if (count <= M) return true;
	return false;
}

int main() {
	int N, M, low = 1, high = 0, result = 0;

	std::cin >> N;
	for (int i = 0; i < N; ++i) {
		int n;
		std::cin >> n;
		arr.push_back(n);
		high = std::max(high, n);
	}
	std::cin >> M;

	while (low <= high) {
		int mid = (low + high) >> 1;

		if (possible(M, mid)) {
			result = std::max(result, mid);
			low = mid + 1;
		}
		else {
			high = mid - 1;
		}
	}

	std::cout << result;
}

우선은 한번에 맞췄습니다.
이분탐색문제를 많이 안풀어봐서 요즘 많이풀고있습니다.
최근에 대회 테스트문제 풀어봤는데, 그리디가 나오더라구요.
그리디도 풀어봐야겠습니다.
사실 그리디가 일반적으로는 거의 초반부에 먼저 푸는유형인데, 저는 이상하게 최대유량문제를 입문으로 풀어서 그리디같은 알고리즘은 엄청 낯섭니다.

💉마치며...

궁금한 부분있으시면 댓글로 질문주세요~