티스토리 뷰

728x90

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;
}
728x90
250x250
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2024/03   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31
글 보관함