Koala - 15기/코딩테스트 준비 스터디
[백준/C++] 1940번: 주몽
nunomi0
2024. 8. 19. 17:47
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;
}