[백준/C++] 1940번: 주몽

https://www.acmicpc.net/problem/1940

 

문제

재료의 수 N(1<=N<=15,000), 갑옷을 만드는데 필요한 수 M(1<=M<=10,000,000), N개의 재료들이 가진 고유한 번호들(1<=X<=100,000)이 공백을 사이에 두고 주어질 때, 두 재료의 고유한 번호를 더해서 M을 만들 수 있는 개수를 출력한다. 

 

풀이

고유한 수를 정렬한 후, 이중 반복문으로 두 수를 더해서 m이 되는 경우의 수를 센다. 이때, 안쪽 루프가 i+1부터 시작하므로, n*2보다는 적은 연산을 한다.

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

int n, m, arr[15010], cnt = 0;

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) cin >> arr[i];
	sort(arr, arr + n);

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