Search

[백준 2422] 한윤정이 이탈리아에 가서 아이스크림을 사먹는데

[백준 2422] 한윤정이 이탈리아에 가서 아이스크림을 사먹는데

Tip

처음엔 교집합으로 풀었는데, 시간 초과
실패 코드
모든 조합을 구하기 위해 iternalscombinations 사용
구한 조합을 완전 탐색하면서 금지된 조합을 포함하는지 확인

풀이 소스 코드

from itertools import combinations import sys si = sys.stdin.readline n, m = map(int, si().split()) array = [i for i in range(1, n + 1)] ice = [[False for _ in range(n + 1)] for _ in range(n + 1)] cnt = 0 for _ in range(m): a, b = map(int, si().split()) # 이렇게 True로 초기화해주면 조건문에 더 간편하게 쓸 수 있음 ice[a][b] = True ice[b][a] = True ice_comb = list(combinations(array, 3)) for i in ice_comb: if ice[i[0]][i[1]] or ice[i[0]][i[2]] or ice[i[1]][i[2]]: continue cnt += 1 print(cnt)
Python