실버5급 문제라서 좀 ... 고생한게 그랬지만..
처음에 했던 방법으로 돌려보니 시간초과가 나서!
시간초과가 났다는 것은 조합을 만들거나, 확인하는 데 있어 필요없는 연산을 너무 많이 했다는거지..
처음에 한 방법
1. N과 M을 입력받고, N은 나중에 3중 for문으로 사용, M은 pair로 받아서 저장
2. 3중 포문을 만들때, vector로 (i, j, k) 가 만들어지고 나서, 있으면 안되는 쌍(M)이 있는지 vector에 find를 써서 .. 확인 -> 이게 엄청 무식한 짓
for pairs:
find1 = find(v.begin(), v.end(), pair->first)
find2 = find(v.begin(), v.end(), pair->second)
find1 & find2 = True 일 경우 있으면 안되는 숫자 2개가 있다는 거지
이렇게 해서 조합을 거르게 시켰었는데 생각해보니 어마어마하다
되선 안되는 조합이 M가지 (0 ~ 10000) 인데 .. 한 조합당 매번 10000번을 체크했다는 거잖아 ..
그래서 속도 빠르게 하려고 별 짓 다했는데, 안되는 방법인 것 같고.
가장 간단하게 풀 수 있는, 체크도 금방 할 수 있는 걸로 !
2차원 배열에 안되는 애들 1로 채워놓고, 3중 for문으로 만들때 참고해서 조합 만들기
//
// Created by 신성준 on 2023/02/12.
//
#include <iostream>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N;
int M;
cin >> N >> M;
int **arr = new int *[N];
for(int i = 0; i < N; i ++){
arr[i] = new int[N];
}
for(int i = 0; i < M; i++){
int a, b;
cin >> a >> b;
arr[a-1][b-1] = arr[b-1][a-1] = 1;
}
int ans = 0;
for(int i = 0; i < N-2; i++){
for(int j = i+1; j < N-1; j++) {
if (arr[i][j] == 1) continue;
for (int k = j+1; k < N; k++){
if(arr[i][k] == 1 || arr[j][k] == 1) continue;
ans++;
}
}
}
cout << ans;
return 0;
}