[BOJ2422 C++] 한윤정이 이탈리아에 가서 아이스크림을 사먹는데

실버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;
}