728x90
문제 1253번
https://www.acmicpc.net/problem/1253
이번 문제는 투포인터를 사용하는 문제이다. N개의 수 중 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있는지 알아내고, 그 개수를 출력하면 된다.
배열에 수를 넣고 해당 수의 개수만큼 정렬을 해준다(투포인터를 이용하려면 정렬은 필수!). 투 포인터 left에는 0, right에는 N-1로 초기화한다. 같은 수의 합으로 나타내면 안 되기 때문에 left가 right보다 작을 때까지 계속해서 반복해주고, left,right를 인덱스로 넣은 값의 합과 찾을 숫자를 비교해준다.
같다면 서로 다른 숫자의 합이 찾는 값이어야하기 때문에 찾을 숫자의 인덱스 i와 left, right를 비교해준다. 둘 다 같지 않다면 좋은 수의 개수를 늘려준 후 반복문을 빠져나오고, i와 같다면 각 left나 right의 값을 이동시켜준다.
찾아야하는 값보다 합이 더 크면 숫자를 줄여줘야하기 때문에 right--를 해주고, 작으면 숫자를 키워야하기 때문에 left++해준다.
그렇게 나온 result값이 좋은 수의 개수이므로 출력해주면 된다.
#include <iostream>
#include <algorithm>
using namespace std;
int N, result = 0;
int num[2000];
int main() {
cin >> N;
for (int i = 0; i < N; i++) {
cin >> num[i];
}
sort(num, num + N);
for (int i = 0; i < N; i++) {
int left = 0, right = N - 1;
int target = num[i]; // 찾을 숫자
while (left < right) {
if (num[left] + num[right] == target) {
if (left != i && right != i) { // 서로 다른 숫자의 합이어야하기 때문에
result++;
break;
}
else if (left == i) {
left++;
}
else if (right == i) {
right--;
}
}
else if (num[left] + num[right] > target) {
right--;
}
else {
left++;
}
}
}
cout << result;
return 0;
}
728x90
'백준 > C++' 카테고리의 다른 글
[C++] 백준 1037번 - 약수 (0) | 2024.05.18 |
---|---|
[C++] 백준 1436번 - 영화감독 숌 (0) | 2024.05.16 |
[C++] 백준 19532번 - 수학은 비대면강의입니다 (0) | 2024.05.14 |
[C++] 백준 2231번 - 분해합 (0) | 2024.05.13 |
[C++] 백준 5635번 - 생일 (0) | 2024.05.12 |