[BOJ] 9024 두 수의 합 C++

개요

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

9024번: 두 수의 합

골드5 난이도 문제다.

풀이

투 포인터로 풀어낼 수 있다.

배열을 정렬 후 양끝에서 각 포인터를 시작한다.

두 포인터의 합이 K보다 큰 경우 큰 쪽 포인터를 작은 쪽으로 이동시키고, 반대로 작은 경우 작은 쪽 포인터를 움직인다.

K와 두 포인터 합의 절댓값을 비교한다.

기존 가장 가까운 합보다 더 가까우면 카운트를 1로 만들고 가장 가까운 값을 바꾸어준다.

가장 가까운 값과 동일한 경우 카운트만 증가시켜 준다. 두 포인터가 만나게 되면 탐색 종료.

 

코드

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
constexpr int LIMIT = 1000002;

int t, n;
int k;
int S[LIMIT];

int main()
{
	cin.tie(0)->sync_with_stdio(0);

	cin >> t;

	for (int i = 0; i < t; i++)
	{
		cin >> n >> k;
		for (int j = 0; j < n; j++)
		{
			cin >> S[j];
		}
		sort(S, S + n);

		int front = 0;
		int back = n - 1;
		int ansSum = 2100000000;
		int sum = 0;
		int cnt = 0;
		while (front < back)
		{
			sum = S[front] + S[back];
			if (abs(k - ansSum) > abs(k - sum))
			{
				ansSum = sum;
				cnt = 1;
			}
			else if (abs(k - ansSum) == abs(k - sum))
			{
				cnt++;
			}

			if (k < sum) back--;
			else front++;

		}
		cout << cnt << "\n";
	}

}