3421. 수제 버거 장인

3421. 수제 버거 장인

처음에 시간초과가 발생할 것 같아서 어떤 방식으로 풀지 굉장히 고민했다.

if(burger[state])==1)

{

return ;

}

이 부분만으로 통과가 될 수 있을까 했는데 다행히 시간초과에서 벗어났다.

비트마스크를 다시 한번 사용해볼 수 있었던 문제.

<정답 코드>

#include<iostream>
#include<string.h>
using namespace std;
int N, M;
int burger[(1 << 20)] = { 0, };
bool chk[21];
void dfs(int state, int n)
{
    if (burger[state] == 1)
    {
        return;
    }
 
    if (n == N)
    {
        burger[state] = 1;
        return;
    }
 
    if ((state & (1 << n)) == 0)
    {
        dfs(state | 1 << n, n + 1);
    }
    dfs(state, n + 1);
}
int main()
{
    //freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tc;
    cin >> tc;
 
    for (int t = 1; t <= tc; t++)
    {
        memset(burger, 0, sizeof(burger));
        memset(chk, false, sizeof(chk));
        cin >> N >> M;
        int R = 0;
        for (int i = 0; i < M; i++)
        {
            int a, b, k;
            cin >> a >> b;
            k = (1 << (a - 1)) | (1 << (b - 1));
            dfs(k, 0);
        }
 
        int ans = 0;
        for (int i = 0; i < (1<<N); i++)
        {
            if (burger[i]==0)
            {
                ans++;
            }
        }
 
        cout << "#" << t << " " << ans << "\n";
    }
    return 0;
}