백준 9024번 두 수의 합(C++)

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

9024번: 두 수의 합

 

문제를 보자마자 이분탐색 투포인터가 떠올라야한다.

난 누적합도 떠올랐는데 이 문제는 모든 조합을 확인하면 TLE임을 알았고 간격의 차이에 따라 계산을 걸러낼 수 있는 양 끝 시작 투포인터를 사용해야한다고 생각했다.

 

2 3 10 14 29

 

가 있다고 하자. 그렇다면 두 수의 합은 lo++를 할 수록 커지고 hi-- 할수록 작아진다.

그러므로 두 수의 합이 k보다 작다면 더 크게 만들어 줘야하니까 lo++ k 보다 크다면 더 작게 만들어야하니 hi-- 이다. 그리고 만약 일치한다면 lo++ hi-- 한다 왜냐하면 이미 최적의 짝을 찾았기 때문이다.

 

이 문제가 골드인 이유는 보통 투포인터나 이분탐색은 정답을 갱신하면서 lo, hi 플러스 마이너스도 결정되는데, 이 문제는 answer++는 다른 로직에 의해 결정된다는 흥미로운 점이 있다.

 

그리고 C++의 경우 입출력 속도 코드를 쓰지 않으면 TLE이다.

 

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

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
    int T; cin >> T;
    vector<int> arr;
    
    for(int t = 0; t < T; t++){
        int n, k;
        cin >> n >> k;
        
        arr = vector<int>(n);
        
        for(int i = 0; i < n; i++){
            cin >> arr[i];
        }
        
        sort(arr.begin(), arr.end());
        
        int hi = n - 1;
        int lo = 0;
        int gap = 100000000;
        int answer = 1;
        while(lo < hi){
            int value = arr[hi] + arr[lo];
            int now_gap = abs(k - value);
            
            if(gap > now_gap){ // 지금갭이 더 작음
                gap = now_gap;
                answer = 1;
            }else if(gap == now_gap){ // 같음
                answer++;
            }
            
            if(value < k){
                lo++;
            }else if(value > k){
                hi--;
            }else{
                hi--;
                lo++;
            }
        }
        
        cout << answer << '\n';
    }
}