백준 2422 한윤정이 이탈리아에 가서 아이스크림을 사먹는데(c++)

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

2422번: 한윤정이 이탈리아에 가서 아이스크림을 사먹는데

주어지는 입력값은 아이스크림의 종류와 조합해서 안 되는 아이스크림의 종류 개수입니다.

예시를 들어 조합해서는 안 되는 아이스크림이 1번, 3번이면 check[3][1], check[1][3]을 true로 바꿔줘야 합니다. 왜냐하면 1번, 3번이나 3번, 1번이나 같은 의미이기 때문입니다. 만약 검사를 하고 check변수가 false이면 개수를 하나씩 늘려주면 됩니다.

시간 복잡도는 O(n^3)으로 풀 수 있게 됩니다.

 

<코드>

#include <iostream>
#include <vector>

using namespace std;
bool check[201][201];
int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        check[a][b] = true;
        check[b][a] = true;
    }

    int 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] || check[j][k] || check[k][i])
                    continue;
                ans += 1;
            }
        }
    }
    cout << ans;
}