[백준/BOJ] 백준 9007번 : 카누 선수

https://www.acmicpc.net/problem/9007

9007번: 카누 선수

 

4개의 반을 0반 ~ 3반으로 나누고, vector<int> people01 에는 0반과 1반 학생의 조합으로 나오는 값들을 저장해 놓고, vector<int> people23 에는 2반과 3반 학생의 조합으로 나오는 값들을 저장해 놓은 뒤 중복된 숫자를 제거하여 두 벡터를 이용해 중간에서 만나는 투포인터를 이용해 문제를 해결했다.

 

이때 중간에서 만다는 투포인터를 두 가지로 나눠서 확인을 했는데, 첫 번째는 중간에서 만나는 left가 people01의 앞쪽 부분, right가 people23의 뒤쪽 부분인 경우이고, 두 번째는 중간에서 만나는 left가 people23의 앞쪽 부분, right가 people01의 뒤쪽 부분인 경우로 나누어서 확인을 했다.

 

코드

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

int tc;
int k, n;
vector<int> people[4];
vector<int> people01; //0반과 1반 학생의 조합으로 나오는 값들
vector<int> people23; //2반과 3반 학생의 조합으로 나오는 값들
vector<int> output;

void Pre() {
	for (int i = 0; i < 4; i++) {
		people[i].clear();
	}
	people01.clear();
	people23.clear();
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> tc;

	for (int t = 0; t < tc; t++) {

		Pre();

		cin >> k >> n;

		for (int c = 0; c < 4; c++) {
			for (int i = 0; i < n; i++) {
				int input;
				cin >> input;
				people[c].push_back(input);
			}
		}

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				people01.push_back(people[0][i] + people[1][j]); //0반과 1반 학생의 조합으로 나오는 값 저장
				people23.push_back(people[2][i] + people[3][j]); //2반과 3반 학생의 조합으로 나오는 값 저장
			}
		}

		sort(people01.begin(), people01.end());
		sort(people23.begin(), people23.end());

		//중복된 값 제거
		people01.erase(unique(people01.begin(), people01.end()), people01.end());
		people23.erase(unique(people23.begin(), people23.end()), people23.end());

		//중간에서 만나는 투포인터를 이용

		//case1
		int left = 0;
		int right = people23.size() - 1;
		int min_diff = 987654321;
		int result = 987654321;
		while (1) {

			if (left == people01.size() || right == -1) {
				break;
			}

			int sum = people01[left] + people23[right];

			//더 근접한 값을 찾았을때
			if (abs(sum - k) < min_diff) {
				min_diff = abs(sum - k);
				result = sum;
			}
			//근접한 정도는 같지만 더 작은 합을 찾았을때
			else if (abs(sum - k) == min_diff && sum < result) {
				result = sum;
			}

			else {
				if (sum > k) {
					//right 줄이기
					right--;
				}

				else if (sum < k) {
					//left 늘리기
					left++;
				}

				else { //k와 차이가 없을때
					break;
				}
			}
		}

		//case2
		left = 0;
		right = people01.size() - 1;
		while (1) {

			if (left == people23.size() || right == -1) {
				break;
			}

			int sum = people23[left] + people01[right];

			//더 근접한 값을 찾았을때
			if (abs(sum - k) < min_diff) {
				min_diff = abs(sum - k);
				result = sum;
			}

			//근접한 정도는 같지만 더 작은 합을 찾았을때
			else if (abs(sum - k) == min_diff && sum < result) {
				result = sum;
			}

			else {
				if (sum > k) {
					//right 줄이기
					right--;
				}

				else if (sum < k) {
					//left 늘리기
					left++;
				}

				else { //k와 차이가 없을때
					break;
				}
			}
		}

		output.push_back(result);
	}

	for (int i = 0; i < output.size(); i++) {
		cout << output[i] << "\n";
	}

	return 0;
}