[C/C++] 백준 9024번 - 두 수의 합

문제

여러 개의 서로 다른 정수 S = {a1, a2, …, an} 와 또 다른 정수 K 가 주어졌을 때, S 에 속하는 서로 다른 두 개의 정수의 합이 K 에 가장 가까운 두 정수를 구하시오. 예를 들어, 10 개의 정수

S = { -7, 9, 2, -4, 12, 1, 5, -3, -2, 0}

가 주어졌을 때, K = 8 에 그 합이 가장 가까운 두 정수는 {12, -4} 이다. 또한 K = 4 에 그 합이 가장 가까운 두 정수는 {-7, 12}, {9, -4}, {5, -2}, {5, 0}, {1, 2} 등의 다섯 종류가 있다.

여러 개의 서로 다른 정수가 주어졌을 때, 주어진 정수들 중에서 서로 다른 두 정수의 합이 주어진 또 다른 정수에 가장 가까운 두 정수의 조합의 수를 계산하는 프로그램을 작성하시오.

입력

프로그램은 표준입력으로 입력을 받는다. 프로그램 입력은 t 개의 테스트 케이스로 구성된다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 정수 t 가 주어진다. 두 번째 줄부터 두 줄에 한 개의 테스트 케이스에 해당하는 데이터가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 두 개의 정수 n 과 K (2 ≤ n ≤ 1,000,000, -108 ≤ K ≤ 108 )가 한 개의 공백을 사이에 두고 입력된다. 두 번째 줄에는 n 개의 정수가 하나의 공백을 사이에 두고 주어지며, 각 정수의 최댓값은 108 이고, 최솟값은 -108 이다. 잘못된 데이터가 입력되는 경우는 없다.

출력

출력은 표준출력(standard output)을 사용한다. 입력되는 테스트 케이스의 순서대로 다음 줄에 이어서 각 테스트 케이스의 결과를 출력한다. 각 테스트 케이스의 출력되는 첫 줄에 입력으로 주어진 n 개의 정수들 중에서 서로 다른 두 정수의 합이 주어진 또 다른 정수 K 에 가장 가까운 두 정수의 조합의 수를 출력한다.

<코드>

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

#define MAX 200000000 // 2억

int t, n, K;
int x;
vector<int> v;

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

	cin >> t;

	while (t--)
	{
		cin >> n >> K;

		for (int i = 0; i < n; i++)
		{
			cin >> x;
			v.push_back(x);
		}

		sort(v.begin(), v.end()); // 배열 정렬

		int left, right, mid, sum, mini, cnt;
		cnt = 0;
		mini = MAX;

		for (int i = 0; i <= v.size() - 2; i++)
		{

			left = i + 1;
			right = v.size() - 1;

			while (left <= right)
			{
				mid = (left + right) / 2;
				sum = v[i] + v[mid];

				if (sum > K)
				{
					right = mid - 1;
				}
				else if (sum <= K)
				{
					left = mid + 1;
				}
					
				if (abs(K - (sum)) < mini)
				{
					cnt = 1;
					mini = abs(K - (sum));
				}
				else if (abs(K - (sum)) == mini)
				{
					cnt++;
				}

			}
		}

		cout << cnt << '\n';
		v.clear(); // 배열 비우기
	}

	
}

 

풀이 방법

n이 최대 100만이니 NlogN의 복잡도로 설계 시 제한시간 내에 코드가 통과가 할 수 있을것이라 생각하여 배열내의 수를 정렬하고 이분탐색으로 차이가 최소가 되는 조합의 수를 찾아서 답을 출력하였습니다. 

 

www.acmicpc.net/problem/9024

9024번: 두 수의 합