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

티스토리 메뉴 펼치기 댓글수0

프로그래밍/삼성 SWEA

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

snoopybox
댓글수0

나의 풀이 :

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 연산을 해서 필터링 한다.

맨위로

https://www.snoopybox.co.kr/2022

신고하기