• 문제

    1

  • 고민

    처음에 섞어먹으면 안되는 조합을 벡터에 저장해서 i, j, k를 골랐을 때 일일이 확인하려고 했다. 당연히 200^3 * 10000이니 시간초과가 났다. 아이스크림 3개를 고르는 것을 오름차순으로 중복 없이 고르면 되기에 3차원 for문으로 구현하면 됐으나, 섞으면 안되는 조합은 배열에 따로 저장해서 체크하는 방식으로 수정했다. 다만 무조건 3개를 섞어야하기 때문에 for문의 조건에 신경을 써야했다.

  • 코드

    #include <iostream>
#include <algorithm>
using namespace std;
  
bool check[201][201];
  
int main() {
	ios::sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int first, second;
		cin >> first >> second;
		if (first > second) {
			swap(first, second);
		}
		check[first][second] = true;
	}
  
	long long ans = 0;
	for (int i = 1; i <= n - 2; i++) {
		for (int j = i + 1; j <= n - 1; j++) {
			for (int k = j + 1; k <= n; k++) {
				if (check[i][j] != true && check[j][k] != true && check[i][k] != true) {
					ans++;
				}
			}
		}
	}
  
	cout << ans << '\n';
  
	return 0;
}