[백준OJ] 9007번 카누 선수

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

9007번: 카누 선수

---

 

-풀이-

4개 각각의 조합을 맞춰가며 최솟값을 찾으면 O(N⁴)이라는 어마어마한 시간이 걸리기 때문에, 다른 방법을 생각해보았다.

1. 먼저 클래스 1,2에서 나올 수 있는 합의 경우를 모두 v1에, 클래스 3,4에서 나올 수 있는 합의 경우를 모두 v2에 push_back한다.

2. 그런 뒤 v1,v2를 정렬한다.

3. v1의 첫번째 원소부터 탐색을 한다. 구해야하는 K와 v1의 탐색중인 원소의 차이를 D라고 하면, v2에서 lower_bound를 이용해서 D보다 크거나 같은 수 중에서 가장 작은 수를 구해준다.

4. 3번에서 구한 결과와 v1에서 탐색중인 원소의 값을 더해주며, K와 근접하다면 갱신해준다. 단. K와의 차이의 절댓값이 같다면 4명의 학생의 합이 작은 수를 구해야 하므로 , 갱신을 할때 조건을 추가해준다.

5. lower_bound의 특성상 크거나 같은수중 가장 작은수를 구하는 함수이므로 , 3번에서 구한 lower_bound의 인덱스보다 한칸 작은칸의 원소도 검사를 해주어야한다.

예를들어

현재 탐색하는 v1의 원소 = 5, 구하고싶은 K의 값 = 10, v2= { 1,2,3,4,50,60,70,} 이라고 한다면,

D의 값은 10-5 = 5가 된다. 이때 lower_bound를 한다면, 50이 결과로 나오게 된다.

1.) v1의 원소+lower_bound로 구한 값 = 5+50 = 55가 되므로, K와의 차이가 45가 나게된다.

2) v1의 원소 + lower_bound로 구한 인덱스-1번째 값 = 5+4 = 9가 되므로, K와의 차이가 1이 나게된다.

 

이처럼 lower_bound로 구한 인덱스의 값만 검사하는게아니라, 한칸 이전의 원소도 검사를 해주어야 정확한 결과가 나온다.

 

-시간복잡도-

v1,v2에 모든 합의 경우를 넣는 로직 O(N²)

v1,v2 정렬 = O(N²logN)

결과값 구하는 로직 =O(N²logN)

 

따라서 총 시간복잡도는 O(N²logN)이 된다.

 

-코드-

 

#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<limits.h>
#define INF INT_MAX;
using namespace std;

int arr1[1000], arr2[1000];
vector<int> v1, v2, v3;
int t, n, m;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin >> t;
	while (t--) {
		v1.clear();
		v2.clear();
		int n, m;
		cin >> m >> n;
		for (int i = 0; i < n; i++) {
			cin >> arr1[i];
		}
		for (int i = 0; i < n; i++) {
			cin >> arr2[i];
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				v1.push_back(arr1[i] + arr2[j]);
			}
		}

		for (int i = 0; i < n; i++) {
			cin >> arr1[i];
		}
		for (int i = 0; i < n; i++) {
			cin >> arr2[i];
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				v2.push_back(arr1[i] + arr2[j]);
			}
		}
		sort(v1.begin(), v1.end());
		sort(v2.begin(), v2.end());

		int result, gap;
		result = gap = INF;
		for (int i = 0; i < n*n; i++) {
			int val = m - v1[i];
			int ind = lower_bound(v2.begin(), v2.end(), val) - v2.begin();
			if (ind == n * n) ind--;
			int total = v1[i] + v2[ind];
			int tgap = abs(m - total);
			if (gap == tgap && result > total) {
				result = total;
			}
			else if (gap > tgap) {
				gap = tgap;
				result = total;
			}
			if (ind != 0) {
				total = v1[i] + v2[ind - 1];
				tgap = abs(m - total);
				if (gap == tgap && result > total) {
					result = total;
				}
				else if (gap > tgap) {
					gap = tgap;
					result = total;
				}
			}
		}
		cout << result << "\n";
	}
	return 0;
}