[ BOJ / C++ ] 3273번 두 수의 합
이번 문제는 투 포인터 알고리즘을 활용해 푸는 문제였다.
투 포인터 알고리즘
- 벡터를 오름차순으로 정렬해준다.
- 두 개의 포인터를 벡터의 첫 인덱스와 끝 인덱스를 가리키게 한다.
- 두 수의 합이 찾는 값과 같다면 cnt를 증가시켜주고 끝 인덱스를 감소시켜준다.
- 두 수의 합이 찾는 값보다 크다면 끝 인덱스를 감소시켜준다.
- 두 수의 합이 찾는 값보다 작다면 첫 인덱스를 증가시켜준다.
- 첫 인덱스가 끝 인덱스와 같아질 때까지 반복한다.
Code
#include <iostream>
#include <algorithm>
#include <vector>
#define MAX 100001
using namespace std;
int n;
int a;
vector<int> arr;
int target;
int cnt=0;
void Input(){
cin>>n;
for(int i=0; i<n; i++){
cin>>a;
arr.push_back(a);
}
cin>>target;
}
void Solution(){
int start=0;
int end=n-1;
sort(arr.begin(), arr.end());
while(start<end){
if(arr[start]+arr[end]==target){
cnt++;
end--;
}
else if(arr[start]+arr[end]>target){
end--;
}
else{
start++;
}
}
cout<<cnt<<endl;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
Input();
Solution();
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#define MAX 100001
using namespace std;
int n;
int a;
vector<int> arr;
int target;
int cnt=0;
void Input(){
cin>>n;
for(int i=0; i<n; i++){
cin>>a;
arr.push_back(a);
}
cin>>target;
}
void Solution(){
int start=0;
int end=n-1;
sort(arr.begin(), arr.end());
while(start<end){
if(arr[start]+arr[end]==target){
cnt++;
end--;
}
else if(arr[start]+arr[end]>target){
end--;
}
else{
start++;
}
}
cout<<cnt<<endl;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
Input();
Solution();
return 0;
}
Author And Source
이 문제에 관하여([ BOJ / C++ ] 3273번 두 수의 합), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@xx0hn/BOJ-C-3273번-두-수의-합저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)