[백준 9024번] 두 수의 합

[백준 9024번] 두 수의 합

www.acmicpc.net/problem/9024

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>
#define INT_MAX 2147483647
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	int t; cin >> t;
	for(int z=0;z<t;z++){
		
		int N, K;
		cin >> N >> K;
		int arr[1000000] = {0,};
		int cnt = 0, mini = INT_MAX;
		
		for(int i=0;i<N;i++) cin >> arr[i];
		sort(arr, arr+N);
		
		int lp = 0, rp = N-1;
		while(lp < rp){
			int a = arr[lp];
			int b = arr[rp];
			if(K == a + b){ lp++; rp--;}
			else if(K < a + b) rp--;
			else lp++;
			
			if(abs(K-(a+b)) < mini){
				mini = abs(K-(a+b));
				cnt = 1;
			}
			else if(abs(K-(a+b))==mini) cnt++;
		}
		
		cout << cnt << '\n';
	}
	return 0;
}

 5/22일자 문제이다. 배열을 정렬한 후 양쪽에 포인터를 두고 K값에 가깝게 만들면 되는 문제이다. 전형적인 투포인터 문제였는데 실수를 알아차리지 못해서 1시간정도 걸렸다. while문의 조건이 lp < rp가 되어야하는데 처음에는 lp != rp로 풀다가 런타임에러(OutOfBounds)를 받았다. 여기에서 발생하는 문제인지 못알아차려서 오래 걸렸다.

 그리고 K값에 가까운 두 정수의 갯수를 구하는 것이기 때문에 정확히 K가 안나오는 경우도 고려해야한다. 따라서 처음 생각은 a+b의 값을 모두 저장해두고 최종 값을 구할 때 살펴보는 방식이었는데 수의 범위가 커서 배열로는 불가능하고 map으로 접근했다가 이것도 안되었다. 고민을 더 하다보니 멍청한 생각이었다는 것을 깨달았다. mini라는 변수를 두고 K와 차이가 더 작은 a+b값이 나오면 mini를 갱신함과 동시에 1부터 다시 세어주면 되는 것이었다. 그래도 다행히 풀긴 풀었다.