[C++] 백준 1940 : 주몽

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

int N, M;
int arr[10000001];
int cnt = 0;

int main(){
  scanf("%d", &N);
  scanf("%d", &M);

  for(int i = 0; i < N; i++){
    scanf("%d", &arr[i]);
  }

  sort(arr, arr + N); // array sort

  // 갑옷은 고유 번호 가지고 있어서 2 pointer 가능
  for(int i = 0; i < N; i++){
    for(int j = N-1; j > i; j--){
      if(arr[i] + arr[j] == M){
        i++;
        cnt++;
      }
    }
  }

  printf("%d", cnt);

  return 0;
}

모든 재료는 고유의 번호를 가지고 있었기 때문에 2 포인터를 이용해서 모든 경우의 수를 구하는 쉬운 구현 문제였다.

빠른 탐색을 위해서는 정렬을 해야하는데 c++ algorithm의 sort 함수를 사용하였다.

for문 2개로 가장 작은 번호랑 매칭되는 큰 수를 구하도록 해서 가장 적게 탐색하도록 짰음.