[BOJ 2422 🥈5] 한윤정이 이탈리아에 가서 아이스크림을 사먹는데 (Python)

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

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

문제

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

입력

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

출력

첫째 줄에, 가능한 방법이 총 몇 개 있는지 출력한다.

예제 입력

5 3
1 2
3 4
1 3

예제 출력

3

 

❌CODE (시간 초과)

from itertools import combinations

# n : 아이스크림 종류의 수 1 <= n <= 200
# m : 섞어먹으면 안되는 조합의 개수 0 <= m <= 10000
n, m = map(int, input().split())

arr = []
for _ in range(m):
    # 섞어 먹으면 안되는 조합의 번호
    a, b = map(int, input().split())
    arr.append((a, b))

l = [int(i) for i in range(1,n+1)]
aa = (list(combinations(l,3)))

count = 0
for i in aa:
    for j in arr:
        if j[0] in i and j[1] in i:
            count += 1
            break
print(len(aa)-count)

⭕CODE

from itertools import combinations

# n : 아이스크림 종류의 수 1 <= n <= 200
# m : 섞어먹으면 안되는 조합의 개수 0 <= m <= 10000
n, m = map(int, input().split())

ice = list(combinations(range(1, n+1), 3))
arr = [[0] * (n+1) for _ in range(n+1)]

for i in range(m):
    x, y = map(int, input().split())
    arr[x][y] = 1
    arr[y][x] = 1
count = 0
for i in ice:
    if arr[i[0]][i[1]] or arr[i[0]][i[2]] or arr[i[1]][i[2]]:
        continue
    count += 1
print(count)

✏️ Comment 

처음에는 단순히 모든 조합을 구하고 이중 for문을 돌면서 확인하려고했다. 그 결과는 시간초과

이차원 리스트를 만들어서  섞어먹으면 안되는 아이들을 1로 변환시켰다.
ex) arr[1][2] = 1 arr[2][1] = 1 -> 1번과 2번은 서로 불가능
이후 모든 조합을 돌면서 하나라도 1 즉 서로 불가능이면 건너뛰고 아닌 조합만 count해주자

 

• 시간복잡도에 관해서 더 고민을 많이 해야겠다. 2중 for문과 in을 사용하니 시간이 많이 걸린다.