[BOJ/C++] 1940 주몽(투포인터)

 

n개의 숫자중에서 2개를 골라 M이 되는 경우의 수를 구하는 문제이다. 이중 반복문을 통해서 모든 경우의 수를 확인하는 방법도 있지만 이렇게 하면 시간 복잡도가 O(n^2)인데 투포인터를 사용한다면 O(n)으로 풀 수 있다. 

투포인터는 두개의 포인터를 사용해 탐색하는 기법이다. 이 문제에서는 정렬 후에 처음과 끝 부분에 포인터를 두고 두 수의 합이 m보다 작다면 앞에 있는 포인터를 옮기고, m보다 크다면 뒤에 있는 포인터를 옮겨 m이 되는 경우를 찾으면 된다

#include<iostream>
#include<algorithm>
using namespace std;
int main(){
    int n, m, cnt=0;
    int clothes[15000];
    cin >> n >> m;
    for(int i=0; i<n; i++){
        cin >> clothes[i];
    }
    sort(clothes,clothes+n);
    int st =0, end = n-1;
    while(st < end){
        //cout << clothes[st] << " " << clothes[end] << " " << cnt << "\n";
        if(clothes[st]+clothes[end]<m){
            st ++;
        }else{
            if(clothes[st]+clothes[end] == m) cnt ++;
            end --;
        }
    }

    cout << cnt;

}