[백준] 2422번 한윤정이 이탈리아에 가서 아이스크림을 사먹는데 - Python / 알고리즘 중급 2/3 - 브루트 포스 - 문제

---

---

---

💡 문제

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

입력

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

출력

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

---

💭 접근

섞으면 안되는 조합을 제외한 아이스크림 3가지를 고르는 경우의 수를 구하는 조합 문제이다. 이때, 입력으로 주어지는 섞으면 안되는 조합들을 저장해놓고, 아이스크림을 뽑으며 섞으면 안되는 아이스크림이 있는지 확인하면 된다.

ans = 0
for i in range(1, n - 1):
    for j in range(i + 1, n):
        if j not in not_mix[i]:
            for k in range(j + 1, n + 1):
                if k not in not_mix[i] and k not in not_mix[j]:
                    ans += 1

이때 아이스크림 3개를 뽑는 조합 문제이기 때문에 간단하게 3중 for문으로 구현할 수 있고, 이때 주의해야 할 점으로는 섞으면 안되는 조합을 저장할 때 list형태가 아닌 set자료형을 이용하여야 in 연산으로 인한 시간초과를 방지할 수 있다.

---

📒 코드

n, m = map(int, input().split())
not_mix = [set() for _ in range(n + 1)]
for _ in range(m):
    a, b = map(int, input().split())
    not_mix[a].add(b)
    not_mix[b].add(a)

ans = 0
for i in range(1, n - 1):
    for j in range(i + 1, n):
        if j not in not_mix[i]:
            for k in range(j + 1, n + 1):
                if k not in not_mix[i] and k not in not_mix[j]:
                    ans += 1
print(ans)

---

💭 후기

아주 간단한 조합문제였다.

---

🔗 문제 출처

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

---