문제 이해 단계
https://www.acmicpc.net/problem/2473
2473번: 세 용액
첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상
www.acmicpc.net
정수로 되어있는 용액이 N개가 주어진다.
이 중에서 3개를 골라 3개의 합이 0에 가장 가까운 경우를 만들 때,
그때의 세 용액을 찾아서 오름차순으로 출력하는 것이 문제이다.
문제 접근 단계
문제는 상당히 간단한데, 일단 수의 범위랑 제한사항부터 살펴보자.
산성 용액과 알칼리 용액으로 구분해 놨지만,
사실상 용액의 범위는 -1,000,000,000 ~ 1,000,000,000까지이다.
범위가 +-10억을 포함하는 상당히 큰 범위이다.
더해야 하는 작업이 있기 때문에 INT형으로는 처리가 안될 것 같다.
그래서 long long 형으로 받아서 처리하도록 하겠다.
그리고 전체 용액의 개수 (N)은 최대 5,000개까지이다.
이 문제의 시간제한이 1초라는 점을 감안할 때
5,000 * 5,000 = 25 * 10^6 이므로 1초가 넘지 않는다.
따라서 이 문제는 O(n^2)까지는 가능하다.
이 점이 핵심인 것 같아 기억하고 넘어가자.
문제 특성으로 보는 유형 유추
이 문제를 푸는 포인트를, 세 가지 용액이라는 점에서 찾으려고 했다.
세 가지 용액을 합쳐서 0에 최대한 근접해야 한다.
3가지씩 고르는 경우의 수이기 때문에 왠지 브루트포스로 되지 않을까?
그럼 시간복잡도가 O(n^3)이라서 시간초과가 나온다.
여기서 든 생각이, O(n^2)까진 문제에서 허용한다.
그러니까 세 가지 용액 중 하나를 고정시켜 두고,
나머지 2개를 움직이면 O(n^2)니까 충분히 가능하지 않을까?
그래서 특정 합 K을 만들어야 하는데, 용액 2개를 고르는 방법으로 생각했다.
투포인터 방식
2개를 선택한다고 했을 때 떠오른 것은 투포인터 방식이었다.
투포인터는 특정 조건을 만족하는 2개의 값을 찾을 때 많이 쓰니까 생각났다.
그런데 여기서 그냥 투포인터를 사용할 순 없고,
규칙적으로 포인터를 이동하기 위해서는 오름차순 정렬이 필요하다.
오름차순으로 정렬한 다음, 첫 번째 용액 다음 인덱스를 두 번째 용액의 시작점으로 두고,
마지막 인덱스를 세 번째 용액의 시작점으로 두자.
그럼 두 번째 용액은 현재 첫 번째 용액 다음으로 가장 작은 값을 가지고 있고,
마지막 용액은 가장 큰 값을 가지고 있다.
이때 3개의 값을 합해서 0보다 큰 값이 나온다면?
당연히 0과 가까워지기 위해서 값을 줄여야 할 것이다.
그러면 간단하게 마지막 용액의 인덱스를 한 칸 앞으로 당기면 된다.
그렇게 하면 오름차순 정렬했기 때문에 수가 작아지기 때문이다.
반대로 0보다 작은 값이 나온다면 합을 올리기 위해
두 번째 용액의 인덱스를 한 칸 올리면 된다.
이런 식으로 첫 번째 용액이 0번 인덱스 ~ N-2번 인덱스까지 훑을 때,
두 번째와 세 번째 용액이 투포인터로 검사해 주면 된다.
자세한 것은 문제 구현 단계에서 코드로 살펴보도록 하자.
문제 구현 단계
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
#define INF 999999999999999999 // long long이라 최대한 큰 값
vector<long long> v; // 용액 리스트
int main(){
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
int N;
cin >> N;
v.resize(N);
for(int i = 0; i < N; i++) cin >> v[i];
long long cnt = INF; // 현재 0과 가장 가까운 값
long long ans[3]; // 정답 3가지 용액
sort(v.begin(),v.end()); // 오름차순 정렬
// 첫번째 용액 0 ~ N-2까지 탐색
for(int i = 0; i < N-2; i++){
long long fixed = v[i]; // 1번째 용액
long long left = i+1; // 2번째 용액
long long right = v.size()-1; // 3번째 용액
// 두 포인터가 같아질때까지 반복
while(left < right){
long long sum = v[left]+v[right]+fixed; // 합
// 합의 절대값이 현재 cnt보다 작으면 갱신
if(abs(sum) < cnt){
cnt = abs(sum);
ans[0] = fixed;
ans[1] = v[left];
ans[2] = v[right];
}
// 합이 0보다 크면 right 포인터 -1
if(sum > 0) right--;
// 합이 0보다 작으면 left 포인터 +1
else if(sum < 0) left++;
// 만약 합이 0이 나온다면 더이상 할 필요없이 바로 출력해주면됨
else {
cout << fixed << " "<< v[left] << " " << v[right];
return 0;
}
}
}
for(int i = 0; i < 3; i++) cout << ans[i] << " ";
}풀이는 간단하다.
입력을 받아 오름차순으로 정렬해 주고,
첫 번째 용액을 0 ~ N-2번째 인덱스까지 탐색시키는 동안
투포인터를 사용하여 탐색을 시킨다.
각 경우의 합의 절댓값이 0과 얼마나 가까운지 확인하여
가장 가까운 값을 cnt에 저장한다.
중간에 합이 0이 나온다면,
그것보다 더 나은 답은 나오지 않기 때문에 바로 그 값을 출력해 준다.
여기서 주의해 줄 점은 long long으로 받아주는 것이다.
시행착오
처음에는 2개의 용액을 고정시키고 한 가지를 고르는 방법으로 했는데,
생각해 보니 이 방식은 여전히 O(n^3)이더라.. 그래서 실패했다.
한 가지로 고정하고 투포인터로 하는 게 생각해 보면 당연한데,
떠오르지가 않았다.. 여전히 많이 부족하다. 잘하고 싶다.
토스아이디
toss.me