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

https://www.acmicpc.net/problem/2422

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

Problem

• 한윤정과 친구들은 이탈리아로 방학 여행을 갔다. 이탈리아는 덥다. 윤정이와 친구들은 아이스크림을 사먹기로 했다. 아이스크림 가게에는 N종류의 아이스크림이 있다.
• 모든 아이스크림은 1부터 N까지 번호가 매겨져있다. 어떤 종류의 아이스크림을 함께먹으면, 맛이 아주 형편없어진다. 따라서 윤정이는 이러한 경우를 피하면서 아이스크림을 3가지 선택하려고 한다. 이때, 선택하는 방법이 몇 가지인지 구하려고 한다.

조건

• 첫째 줄에 정수 N과 M이 주어진다. N은 아이스크림 종류의 수이고, M은 섞어먹으면 안 되는 조합의 개수이다. 아래 M개의 줄에는 섞어먹으면 안 되는 조합의 번호가 주어진다. 같은 조합은 두 번 이상 나오지 않는다. (1 ≤ N ≤ 200, 0 ≤ M ≤ 10,000)

SOL

조합하면 안되는 조합을 거르는 문제이다(민트 +초코)

조합표에다가, 조합하면 안되는걸 표시해두고, 조합의 수를 뽑아봤을때, 그 조합표에 만약 있다면 , 그 조합은 절대 섞으면 안된다.

#한융정이~`
# 미리 표기하는 방식!!
from itertools import combinations
import sys
input= sys.stdin.readline
N,M= map(int,(input().split()))
ice =[[False]*N for _ in range(N)]

for i in range(M):
    a,b=map(int,input().split())
    ice[a-1][b-1] = True
    ice[b-1][a-1] = True
ans=0
for combi in combinations(range(N),3):
    if ice[combi[0]][combi[1]] or ice[combi[1]][combi[2]] or ice[combi[0]][combi[2]]:
        continue
    ans+=1
print(ans)