[백준 1940번] 주몽 (C++)

문제링크 : https://www.acmicpc.net/problem/1940

1940번: 주몽

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = INT_MAX;

int N, M, arr[15001];

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> N >> M;
    for(int i=0; i<N; i++) cin >> arr[i];
    sort(arr, arr+N);

    int l=0, r=N-1;
    int cnt = 0;
    
    while(l<r)
    {
        int tmp = arr[l] + arr[r]; //목표값
        if(tmp == M) cnt++;

        if(tmp < M) l++; //더 크게
        else r--; //더 작게
    }
    
    cout << cnt;
    return 0;
}

 

간단한 두 포인터 문제이다.

우선 두 포인터 알고리즘 사용을 위해 입력받은 배열을 정렬해준다.

 

이후에 포인터 l과 r을 움직이며, 해당 위치 값의 합이 M과 같을 때 카운팅을 해준다.

만약 합이 M보다 작다면 값을 증가시 위해 l 포인터를 증가시키고,

M보다 크거나 같다면  값을 감소시키기 위해 r 포인터를 증가시킨다.