백준 2467, 2470번 C++ 풀이

문제

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

 

시간 제한	메모리 제한	solved.ac 티어
1초	128MB	골드 5

---

풀이

이번에도 밀린 문제 정리하기이다. 이번 문제는 투포인터 문제이다. 직관적으로 떠올릴 수 있는 방법은 중첩반복문을 통해 브루트포스를 하는 것이지만, 시간복잡도가 O(N^2)가 나오고, N은 최대 10만이기 때문에 불가능한 방법이다. 따라서 투포인터를 통해 O(N)의 시간복잡도로 탐색하면 될 것이다. 용액의 특성값을 오름차순으로 정렬하고, 포인터를 각각 맨 앞과 맨 뒤에 둔다. 입력은 세가지 경우로 나뉜다. 

• 모두 양수인 경우
• 모두 음수인 경우
• 음수 양수 섞인 경우

어떻던 간에 모두 양수라면 오른쪽 포인터(맨 뒤에 있던 포인터)를 왼쪽으로 당겨올수록 0에 가까워 질 것이고, 모두 음수라면 왼쪽 포인터(맨 앞, 그러니까 인덱스가 0인 포인터)를 오른쪽으로 당겨올수록 0에 가까워 질 것이다. 여기에서 각 포인터가 가리키는 값의 합이 음수라면 왼쪽 포인터를 오른쪽으로, 양수라면 오른쪽 포인터를 왼쪽으로 움직이다보면 답을 얻을 수 있을 것이다.

코드

#include <bits/stdc++.h>
#define ALL(X) X.begin(), X.end()
using namespace std;
using pii = pair<int,int>;

int n;
vector<int> v;

void input(){
    cin >> n;
    v.resize(n);
    for(int& x : v) cin >> x;
    sort(ALL(v));
}
    
void sol(){
    pii answer;
    int l = 0, r = n-1, diff = INT32_MAX, cur_diff;

    while(l < r) {
        cur_diff = v[l]+v[r];
        if (diff > abs(cur_diff)){
            diff = abs(cur_diff);
            answer = {v[l], v[r]};
        }
        if (cur_diff < 0) l++;
        else r--;
    }
    auto& [a,b] = answer;
    cout << a << ' ' << b;
}

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

 

 

---

2467번 풀이

(25.01.53 14:53 추가)

solved.ac 클래스 문제를 뒤져보던 중,  2467번의 문제가 해당 문제와 완전히 동일하다는 것을 알았다. 풀이가 같을 뿐만 아니라 문제자체도 설명을 위한 용액의 특성값 순서가 좀 다를 뿐 완전히 동일한 문제임을 알았다. 완전히 같은 문제이기 때문에 위에서 설명한 대로 풀이하면 된다.