https://www.acmicpc.net/problem/3273
시간 제한 | 메모리 제한 | solved.ac 티어 |
1초 | 128MB | 실버 3 |
문제
n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 (ai, aj)쌍의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 수열의 크기 n이 주어진다. 다음 줄에는 수열에 포함되는 수가 주어진다. 셋째 줄에는 x가 주어진다. (1 ≤ n ≤ 100000, 1 ≤ x ≤ 2000000)
출력
문제의 조건을 만족하는 쌍의 개수를 출력한다.
단순히 브루트포스의 방법으로 두 수의 합을 확인하면 시간초과가 날 것이다. 숫자가 10만개가 들어오기 때문에, 브루트포스로 접근하여 이중 반복문을 돌렸다가는 100억번을 돌고, 이는 1초를 넘어갈 것이 뻔하다. 따라서 이런 경우에 O(n)으로 처리할 수 있는 투포인터 알고리즘으로 접근한다 (C언어의 그 포인터와 어쩌면 유사하겠다).
입력받은 수열을 오름차순으로 정렬하고, 포인터 하나는 맨 앞에, 남은 하나는 맨 오른쪽에 위치시킨다. 이후 앞의 포인터는 뒤로, 뒤의 포인터는 앞으로 이동하면서 합이 X가 되는 경우를 모두 세면 된다. 이동 횟수가 배열의 길이와 같기 때문에, 이 알고리즘은 O(n)이 되기 때문에 제한 시간안에 끝낼 수 있다.
#include <bits/stdc++.h>
using namespace std;
int n, target;
vector<int> v;
void input() {
cin >> n;
v.resize(n);
for(int& x : v) cin >> x;
cin >> target;
sort(v.begin(), v.end());
}
void sol() {
int cnt = 0, sum = 0, lo = 0, hi = n - 1;
while(lo < hi) {
sum = v[lo] + v[hi];
if (sum > target) hi--;
else if (sum < target) lo++;
else {
cnt++;
hi--;
lo++;
}
}
cout << cnt;
}
int main () {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
input();
sol();
}
'coding_test > BAEKJOON' 카테고리의 다른 글
백준 16926번 C++ 풀이 (0) | 2022.05.22 |
---|---|
백준 16194번 C++ 풀이 (0) | 2022.05.22 |
백준 1339번 C++ 풀이 (0) | 2022.05.22 |
백준 1449번 C++ 풀이 (0) | 2022.05.22 |
백준 2217번 C++ 풀이 (0) | 2022.05.22 |