[C++] 백준 9007번: 카누 선수

문제 링크

9007번: 카누 선수

문제 요약

4개의 반에 속하는 학생들의 몸무게가 주어진다. 각 반에서 학생을 한 명씩 뽑아서 팀을 만들 때, 몸무게의 합이 K에 가장 근접하도록 만들어야 한다. 몸무게 합의 차가 동일한 경우(K가 300이고 합이 298, 302인 경우)에는 작은 쪽을 출력해야 한다.

접근 방법

합이 0인 네 정수 문제와 비슷하게 Meet in the Middle로 접근하면 됩니다. $O(N^4)$ 풀이는 무조건 TLE를 받을 것이기 때문에, 둘씩 반으로 나눠서 합을 모두 구해준 다음에 이분탐색을 이용해야 합니다.

합이 0인 네 정수 문제의 경우 합이 0인 경우를 모두 찾는 것이기 때문에 그냥 upper_bound에서 lower_bound를 빼주면 되지만, 이 문제는 해가 없는 경우 가장 가까운 값을 출력해야 합니다. 따라서 일단 lower_bound를 먼저 사용해야 합니다. lower_bound는 찾고자하는 값이 있다면 그 값을 찾아주고, 없다면 그보다 큰 값 중 최소인 값을 찾아줍니다. lower_bound를 통해서 인덱스를 계산하고, K와의 차의 절댓값이 더 작을때마다 갱신해 줍니다.

그리고 그보다 하나 작은 인덱스의 값에서도 똑같이 진행해주면 됩니다. lower_bound의 특성상 같거나 큰 값만 찾아주는데, K와의 차의 절댓값이 동일하다면 보다 작은 값이 우선되기 때문입니다. 이때는 차의 절댓값이 현재보다 작은 경우와 같은 경우 모두 갱신해줘야 합니다.

코드

#include <bits/stdc++.h>

using namespace std;

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

	int t;
	cin >> t;

	while (t--)
	{
		int k, n;
		cin >> k >> n;

		vector<int> a(n), b(n), c(n), d(n), sum;

		for (int i = 0; i < n; i++) cin >> a[i];
		for (int i = 0; i < n; i++) cin >> b[i];
		for (int i = 0; i < n; i++) cin >> c[i];
		for (int i = 0; i < n; i++) cin >> d[i];

		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				sum.push_back(a[i] + b[j]);

		sort(sum.begin(), sum.end());

		int ans = 0, diff = INT_MAX;
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				int num = c[i] + d[j];

				int pos = lower_bound(sum.begin(), sum.end(), k - num) - sum.begin();

				if (pos == sum.size())
				{
					pos--;
					if (abs(sum[pos] + num - k) < diff)
					{
						ans = sum[pos] + num;
						diff = abs(sum[pos] + num - k);
					}
					continue;
				}

				if (abs(sum[pos] + num - k) < diff)
				{
					ans = sum[pos] + num;
					diff = abs(sum[pos] + num - k);
				}

				if (pos >= 1)
				{
					pos--;
					if (abs(sum[pos] + num - k) <= diff)
					{
						ans = sum[pos] + num;
						diff = abs(sum[pos] + num - k);
					}
				}
			}
		}

		cout << ans << '\n';
	}

	return 0;
}