[백준/C++] 3273번. 두 수의 합
[백준/C++] 3273번. 두 수의 합
1. 문제
n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 (ai, aj)쌍의 수를 구하는 프로그램을 작성하시오.
2. 입력
첫째 줄에 수열의 크기 n이 주어진다. 다음 줄에는 수열에 포함되는 수가 주어진다. 셋째 줄에는 x가 주어진다. (1 ≤ n ≤ 100000, 1 ≤ x ≤ 2000000)
3. 출력
문제의 조건을 만족하는 쌍의 개수를 출력한다.
4. 풀이
투 포인터
문제- 두 개의 인덱스를 가지고 범위를 좁혀가면서 조건에 맞는 인덱스를 찾는다.
- 값을 모두 입력 받은 후에 먼저 배열을 정렬한다.
- 양쪽에서 포인터를 좁혀가면서 탐색을 할 것이기 때문에 배열이 정렬되어 있어야한다.
arr[start] + arr[end]
값과target
값을 비교한다.arr[start] + arr[end] == target
: 원하는 값을 찾았기 때문에 결과를 추가하고 양쪽 인덱스를 좁힌다.arr[start] + arr[end] < target
: 원하는 값보다 작기 때문에 더 큰 값을 찾아야 한다.start
를 늘려 값을 키운다.arr[start] + arr[end] > target
: 원하는 값보다 크기 때문에 더 작은 값을 찾아야 한다.end
줄여 값을 줄인다.
5. 처음 코드와 달라진 점
while-loop
조건문을start <= end
라고 작성해서 수정해주었다.start <= end
라고 작성하면target = 12
이고arr[start==end] = 6
이면 실제로는 6이 하나밖에 없어도 순서쌍으로 나와서 개수가 더해진다.
6. 코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n, target;
vector<int> arr;
int main() {
cin.tie(NULL);
ios_base::sync_with_stdio(false);
cin >> n;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
arr.push_back(x);
}
cin >> target;
sort(arr.begin(), arr.end());
int start = 0, end = n-1;
int answer = 0;
while (start < end) {
int sum = arr[start] + arr[end];
if (sum == target) {
answer++;
start++;
end--;
}
else if(sum < target) {
start++;
}
else {
end--;
}
}
cout<<answer;
}
Author And Source
이 문제에 관하여([백준/C++] 3273번. 두 수의 합), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@e7838752/boj3273저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)