[SWEA][Python3] 3421. 수제 버거 장인

나의 풀이 :

T = int(input())

for tc in range(1, T + 1):

N, M = map(int, input().split())

bad_set = set()

for _ in range(M):

a, b = map(int, input().split())

k = 2**(a-1) + 2**(b-1)

bad_set.add(k)

ans = 0

for i in range(2**N):

for bad in bad_set:

if i & bad == bad:

break

else:

ans += 1

print('#{} {}'.format(tc, ans))

한마디 :

당연히 Timeout일 것으로 생각하고 Brute-Force 답안을 제출했는데 의외로 통과되었다. 부분집합의 갯수는 2**N 만큼 존재하는데, 각각 피해야 하는 조합과 Bitwise AND 연산을 해서 필터링 한다.