1940

 

 

문제 요약

 

갑옷은 두 개의 재료로 만들어진다. 

 

두 재료의 고유한 번호를 합쳐서 M이 되면 갑옷이 만들어진다. 

 

입력

 

N개의 재료( 1 <= N <= 15,000)의 개수가 주어진다. 

 

갑옷을 만드는 데 필요한 수 M ( 1 <= M <= 10,000,000).

 

N개의 재료들이 가진 고유 번호들이 주어진다.  (100,000 보다 작거나 같은 자연수이다.)

 

출력

 

만들 수 있는 갑옷의 개수.

 

 

풀이

 

정리를 해보면 다음과 같다.

 

재료의 수가 주어지고, 2개를 활용하여 갑옷을 만드는데, 고유 번호의 합이 갑옷의 필요 수와 동일한 값이 몇 개가 만들어질 수 있는지 구하는 문제이다. 

 

주어진 수에서 순서 상관없이 2개를 뽑아 m과 같다면 카운트를 증가시키면 된다. 

 

조합이며, 이는 2개라는 적은 수이기 때문에 중첩 for문을 통해 구현할 수 있다.

 

#include <bits/stdc++.h>

using namespace std;

int n, m, te[15004], cnt;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> m;

    for (int i = 0; i < n; i++) cin >> te[i];
    
    if(m > 200000) cout << 0 << '\n';
    else{
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if(te[i] + te[j] == m) cnt++;
            }
        }
        cout << cnt <<'\n';    
    }
    

    return 0;
}