백준 1940

* 출처 : [10주완성 C++ 코딩테스트 | 알고리즘 IT취업]

* 조건

▶ 갑옷을 만드는 재료들은 각각 고유한 번호를 가짐
▶ 갑옷은 두 개의 재료로 만듦, 두 개의 재료의 고유한 번호를 합쳐서 M이 되면 갑옷을 만듦
▶ M의 범위는 1 <= M <= 10,000,000
▶ N개(1 <= N <= 15,000) 개의 재료와 M이 주어졌을 때 몇 개의 갑옷을 만들 수 있는지 구하시오
▶ 첫째 줄 : 재료의 개수 N이 주어짐
▶ 두 번째 줄 : 갑옷을 만드는데 필요한 수 M
▶ 세 번째 줄 : N개의 재료들이 가진 고유한 번호들이 공백을 사이에 두고 주어짐
(100,000보다 작거나 같은 자연수)

* 중요한 점

▶ N개의 재료 중 2개 고르고 고유한 번호(10만 이하)
▶ N개 중 2개를 고름 (combination, 순서가 상관없음)

nC2

* 코드

#include <bits/stdc++.h>
using namespace std;
int n, m, a[150001], cnt;
int main() {
    ios_base::sync_with_stdio(false);
	cin.tie(NULL);
    cin >> n >> m;
    for(int i = 0; i < n; i++) cin >> a[i];
    sort(a, a + n); 
    if(m > 200000) cout << 0 << "\n";
    else {
        for(int i=0; i<n; i++) {
            for(int j = i + 1; j < n; j++) {
                if(a[i] + a[j] == m)cnt++;
            }
        }
        cout << cnt << "\n";
    }
}

* 정리

1) if(m > 200000) cout << 0 << "\n";
▶ n + n 더하면 200,000이하로만 나와야함 그 이상은 없어야 함
▶ 시간초과 고려

2) 순서와 상관없이 2개 뽑음
▶ 2개의 재료를 뽑고 counting (if(a[i] + a[j] == m)cnt++;)

 for(int i=0; i<n; i++) {
            for(int j = i + 1; j < n; j++) {
                if(a[i] + a[j] == m)cnt++;
            }
        }