2422번

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

처음에는 오름차순으로 모든 경우의 수를 구하고, 기저 조건에서 모든 M번의 for문을 수행하면서 섞으면 안되는 조합이 있는지를 검사하는 

방식을 구현했었다. 그런데 최악의 경우 200개 중에서 3개를 고르는 조합의 수 * 10000번의 for문을 돌게 되면 시간초과가 발생하게 된다.

따라서 M이라는 변수는 배열을 이용해서 저장하고, 최대한 200이라는 N의 값을 이용해서 문제를 풀어야 했다.

그래서 3개의 아이스크림만 고르면 되기 떄문에 first second third 를 재귀함수를 이용해서 구하면서 마지막에 먹어도 되는 조합인지 아닌지

를 판단하는 방식으로 코드를 구현했다.

<정답 코드>

#include<iostream>
#include<vector>
using namespace std;
int N, M;
int e[201][201];
int ans;
int selected[201];
void go(int before,int first, int second, int third)
{
    if (first!=0 && second !=0 && third !=0)
    {
        if (e[first][second] == 1)
            return;
 
        if (e[first][third] == 1)
            return;
 
        if (e[second][third] == 1)
            return;
 
        ans++;
        return;
    }
 
    for (int i = before; i <= N; i++)
    {
        if (selected[i] == 0)
        {
            selected[i] = 1;
            if (first == 0) {
                go(i+1, i, 0, 0);
                selected[i] = 0;
                continue;
            }
 
            if (second == 0) {
                go(i + 1, first, i, 0);
                selected[i] = 0;
                continue;
            }
 
            if (third == 0) {
                go(i + 1, first, second, i);
                selected[i] = 0;
                continue;
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> N >> M;
    for (int i = 0; i < M; i++)
    {
        int a, b;
        cin >> a >> b;
        e[a][b] = 1;
        e[b][a] = 1;
    }
 
    go(1, 0, 0, 0);
 
    cout << ans << endl;
    return 0;
}