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

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

문제 번호 : 2422
문제 출처 : https://www.acmicpc.net/problem/2422

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

 

---

---

Code

import sys

n, m = map(int, input().split())
answer = n * (n - 1) * (n - 2) // 6
nomat = [set() for _ in range(n)]
for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    answer -= (n-2) - len(nomat[a-1] | nomat[b-1])
    nomat[a-1].add(b)
    nomat[b-1].add(a)

print(answer)

---

Idea

1. 초기 answer 값은 \( {}_n \mathrm {C}_3 \) 을 수로 나타낸 것이다.
2. nomat 리스트에는 각 맛 별로 조합이 좋지 않은 맛을 넣는다.
3. 2 가지가 정해진 상황에서 나머지 한 가지 맛을 고르는 경우의 수는 n - 2 이다.
4. 그 전에 경우의 수에서 없앤 경우의 수는 합집합의 길이가 된다.

예제 입력을 넣었을 때를 예시로 들면 다음과 같다.

    1. 모든 경우의 수는 5가지 맛 중 3가지를 뽑는 경우로 총 10이다.  
    2. 처음 (1, 2, X) 를 뽑는 경우의 수는 3가지이므로 전체 경우의 수에서 3을 빼준다.  
    3. (3, 4, X) 를 뽑는 경우의 수 중 전에 뽑은 경우가 없으므로 `nomat\[2\]`와 `nomat\[3\]`의 합집합의 길이는 0이다.  
    4. (1, 3, X) 를 뽑는 경우에는 (1, 2, 3) 인 경우와 (1, 3, 4) 인 경우를 그 전의 입력에서 뺐으므로 전체 경우의 수에서 1만 빼준다.

처음에 코드 제출했을 때는 파이썬 언어에서 시간 순위 1등이었는데 글 적을 때 되니까 밀려났다.