티스토리 뷰

https://www.acmicpc.net/problem/3273

 

3273번: 두 수의 합

n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는

www.acmicpc.net

C++ 투포인터

합이 X인 두 수의 개수를 구하는 문제

 

접근방법 

우선 오름차순 정렬

두 포인터를 양끝에 두고 시작하여

두 수의 합이 X보다 크면 끝점을 한 칸 앞으로

X보다 작으면 시작점을 한 칸 뒤로

X이면 cnt를 1 증가시키고 시작점은 한칸 뒤로 끝점은 한칸 앞으로

 

오답노트

처음엔 두개의 포인터를 0,1번째에 두고 시작해서 무한루프에 빠지는 경우가 생겼었다.

 

소스코드

#include <iostream>
#include <algorithm>
using namespace std;

int main(){
    //input & init
    int N;
    cin >> N;
    
    int arr[N];
    
    for(int i = 0 ; i < N ; i++){
        cin >> arr[i];
    }
    
    int x;
    cin >> x;
    
    //process
    
    sort(arr, arr+N);
    
    if(N == 1){
        cout << 0 << "\n";
        return 0;
    }
    
    int s,e;
    s = 0;
    e = N-1;
  
    int cnt = 0;
    int sum;
    while(s < e){
        sum = arr[s] + arr[e];
        if(sum > x){
            e--;
        }else if(sum == x){
            cnt++;
            s++;
            e--;
        }else{
            s++;
        }
    }
    
    cout << cnt << "\n";
    
    return 0;
}
댓글
댓글쓰기 폼