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

문제

---

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

코드

---

My answer(시간초과)

import sys
from itertools import combinations
input=sys.stdin.readline

n,m=map(int,input().split())
tmp=[i for i in range(1,n+1)]

nc,cnt,res=[],0,0
for i in range(m):
    nc.append(list(map(int,input().split())))

for i in combinations(tmp,3):
    for j in nc:
        if(len(set(j) & set(i)) !=2):
            cnt+=1
    if(cnt==3):
        res+=1
    cnt=0
print(res)

Another answer

import sys
from itertools import combinations

input = sys.stdin.readline

n, m = map(int, input().split())
ice = [[False for _ in range(n)] for _ in range(n)]
for i in range(m):
    i1, i2 = map(int, input().split())
    ice[i1 - 1][i2 - 1] = True
    ice[i2 - 1][i1 - 1] = True

result = 0

for i in combinations(range(n), 3):
    if ice[i[0]][i[1]] or ice[i[0]][i[2]] or ice[i[1]][i[2]]:
        continue
    result += 1
print(result)

풀이

---

이 문제도 우선 브루트포스 문제다. 모든 조합을 선택해놓고 거기서 안되는것을 빼면 된다. 내 코드와 아래코드 전체적인 것은 똑같은 데 세부적인 부분이 달랐다. 내 코드는 뭔가 직관적으로 하기위해서 조합을 선택하고 그 조합과 먹을 수 없는 아이스크립 집합을 교집합 처리해서 구했는데, 결과는 제대로 나왔는데 시간초과가 떴다. 아래 코드는 그냥 조합에 먹으면 안되는 집합이 들어가있으면 continue하는 식으로 처리해서 게산을 했다. 아마 내 코드에서는 일일이 집합으로 바꿔주고 이중반복문 안에서 교집합을 처리하다보니 시간초과가 걸린 것 같다.