[SWEA] 11446번 : 사탕 가방

🔗 문제 링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AXdHxTNqC2IDFAS5

✍️ 문제 풀이

해당 문제는 이진 탐색 문제로, 어떤 조건을 만족할 때의 가방 개수의 최대치를 구해야 하기 때문에 파라메트릭 서치로 풀 수 있다.

1) 사탕 종류 개수 n과 가방에 정확히 들어있어야하는 사탕 개수 m을 입력받아 저장한다.

2) candies 벡터에 각 사탕 종류별로 몇 개의 사탕이 있는지 입력받아 저장한다.
이 때 가장 개수가 많은 종류의 사탕의 개수를 max에 저장한다.

3) 이진 탐색(파라메트릭 서치)을 실행해 end가 start보다 작지 않은 동안 아래 과정을 반복한다.

• start = 0, end = max로 지정한다.
  • 가방을 하나도 못 만들 경우가 최소
  • 가방 안에 1개의 사탕만 들어있어야 하면, 가장 많은 종류만 하나 넣을 때가 최대
• mid를 start + (end - start) / 2로 초기화 한다.
• 현재 가방 개수가 mid일 때, candies 벡터에 저장된 모든 종류의 사탕 개수에 대해 mid로 나누면 현재 사용되는 각 종류 별 사탕 개수를 알 수 있다.
• 이 각 종류의 사탕 개수들을 curCount에 더해 현재 가방이 mid개일 때 curCount(총 사탕 개수)를 m과 비교한다.
  • curCount < m : 가방 개수가 너무 많아 필요한 사탕 개수 충족 X
    • 따라서 mid 이상 개수는 불가능하므로 그 아래부터 탐색한다. (end = mid - 1)
  • curCount >= m : 가방 개수가 딱 맞거나 너무 적으면 필요한 사탕 개수는 충족 O
    • 가방 개수의 최대값을 구해야하므로 일단 정답을 mid개로 저장해놓고 (answer = mid), 그 위부터 다시 탐색한다. (start = mid + 1)

4) 이진 탐색이 끝난 뒤 answer가 최대 가방 개수이므로 이를 출력한다.

🖥️ 풀이 코드

##include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>
#include <queue>
#include <cmath>

using namespace std;
vector<long long> candies;

long long binarySearch(long long m, long long max)
{
	long long start = 1, end = max;
	long long answer = 0;

	while (end >= start)
	{
		long long mid = start + (end - start) / 2;

		// 각 사탕 개수를 현재 가방 개수로 나누면, 해당 가방 개수일 때 사용해야하는 각 사탕 개수를 알 수 있음.
		long long curCount = 0;
		for (int i = 0; i < candies.size(); i++)
			curCount += candies[i] / mid;
		
		if (curCount < m)		// 가방 개수 너무 많으면 한 가방 내 사탕 개수 못 채움 -> mid 이상 개수는 불가능. 그 아래 탐색
			end = mid - 1;
		else                   //  가방 개수 딱 맞거나 너무 적으면 한 가방 내 사탕 개수 채움 -> 현재 가방 개수를 answer로 설정하고 그 위 값도 탐색
		{
			answer = mid;
			start = mid + 1;
		}
	}
	return answer;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(); cout.tie();

	int t;
	cin >> t;

	for (int i = 0; i < t; i++)
	{
		long long n, m;
		cin >> n >> m;
		long long max = 0;
		for (int j = 0; j < n; j++)
		{
			long long num;
			cin >> num;
			candies.push_back(num);

			if (max < num)
				max = num;
		}

		cout << '#' << i + 1 << ' ' << binarySearch(m, max) << endl;
		candies.clear();
	}
}