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

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

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

문제

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

입력

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

출력

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

예제 입력 1 

5 3
1 2
3 4
1 3

예제 출력 1 

3

 

✔️ Code

from itertools import combinations
from pickle import TRUE
n, m = map(int, input().split())

ice = [[False]* 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)

 

✏️ Comment 

• 조합하면 안되는 아이스크림을 리스트에 저장해준다. 예를 들면 (1, 2) 와 (1, 3) 이 조합하면 안된다고 했을 때, ice[0][1] = True, ice[0][2] = True (리스트의 인덱스가 0부터 시작하므로 각각 아이스크림 번호에서 -1 씩 해주었다.)
• combination을 사용해서 모든 아이스크림의 조합을 구해준다.

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

• 그리고 각 조합의 경우들에 대해서 True가 존재한다면 (즉, 조합하면 안되는 아이스크림들이 조합된 경우라면) continue로 넘어가고 그렇지 않다면 result += 1 해준다.

⇒ combination 사용법이 살짝 헷갈렸다. 이 외에도 product 같은 것도 많이 쓰이는 것 같은데, 확실히 공부해둬야 편할 것 같다.