[ACM-ICPC][BOJ] 9007 - Canoe Racer

안녕하세요.

여행벌입니다.

오늘은 ACM-ICPC 2012 예선전 문제인 'Canoe Racer' 문제를 다뤄보겠습니다.

---

[문제해석]

1. 특정 숫자 K 와 n 개 씩 4개의 숫자 배열이 주어졌을 때, 4개의 배열에서 하나씩 숫자를 뽑아 합했을 때, 특정 숫자 K과 가장 근접한 경우를 출력하라. (K과 가장 근접한 숫자가 2개 이상일 때는 더 작은 숫자를 출력하라.)

 

[알고리즘설계]

n 개 씩 4개의 숫자 배열을 각각 A,B,C,D 배열이라고 하자.

n이 최대 1000 이므로, A,B,C,D 배열에서 4중 for 문으로 1개씩 뽑아 모든 경우의 수를 다 구한다면, O(n^4)으로 당연히 시간 초과에 걸릴 것이다.

따라서, 우리는  A,B / C,D 배열을 2개씩 합쳐서 AB / CD 배열을 따로 만들고, 그 배열을 순회하며 답을 찾아줄 것이다.

또, AB배열을 순회하며, CD 배열에 있는 원소와의 합이 K와 근접한 숫자를 찾아야하는데, Linear Search 보다는 AB / CD 배열을 Sorting 한 후, Binary Search 를 이용해 답을 찾아줄 것이다.

 

그렇다면, O(n^4)의 복잡도가 O(n^2)으로 낮아진다.

#include<cstdio>
#include<algorithm>

int map[4][1000];

int ab[1000000];
int cd[1000000];

using namespace std;

int abs(int n) {
	if (n < 0)
		return -n;
	return n;
}

int main(void) {
	int test_case;
	scanf("%d", &test_case);

	for (int i = 0; i < test_case; i++) {
		int answer, ninput;
		scanf("%d %d", &answer, &ninput);

		for (int j = 0; j < 4; j++)
			for (int k = 0; k < ninput; k++) 
				scanf("%d", &map[j][k]);
		
		
		for (int j = 0; j < ninput; j++)
			for (int k = 0; k < ninput; k++){
				ab[ninput * j + k] = map[0][j] + map[1][k];
				cd[ninput * j + k] = map[2][j] + map[3][k];
			}

		sort(ab, ab + ninput * ninput);
		sort(cd, cd + ninput * ninput);


		int flag = 0, total_result = 999999999;
		int length = ninput * ninput;
		// Binary Search 
		for (int j = 0; j < length; j++) {

			int result = 999999999;
			int left = 0;
			int right = length - 1;

			while (left <= right) {
				int mid = (left + right) / 2;
				int temp = ab[j] + cd[mid];

				if (temp == answer) {
					printf("%d\n", answer);
					flag = 1;
					break;
				}
				else if (temp < answer) {
					left = mid + 1;
				}
				else{
					right = mid - 1;
				}

				if (abs(answer - result) > abs(answer - temp))
					result = temp;
				else if(abs(answer - result) == abs(answer - temp))
					result = min(result, temp);
			}

			if (flag)
				break;

			if (abs(answer - result) < abs(answer - total_result))
				total_result = result; 
			else if(abs(answer - result) == abs(answer - total_result))
				total_result = min(result, total_result);
		}
		if (flag)
			continue;

		printf("%d\n", total_result);
	}
}

배열을 2개씩 합쳐주면서 복잡도를 완전히 낮춰줄 수 있는데, 기존에 풀었던 문제와 유사해서 쉽게 문제를 해결할 수 있었다.

---