BOJ 2422

Input

첫째 줄에 정수 N과 M이 주어진다. N은 아이스크림 종류의 수이고, M은 섞어먹으면 안 되는 조합의 개수이다.

아래 M개의 줄에는 섞어먹으면 안 되는 조합의 번호가 주어진다. 같은 조합은 두 번 이상 나오지 않는다. (1 ≤ N ≤ 200, 0 ≤ M ≤ 10,000)

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
s = [[0]*(n+1) for _ in range(n+1)]

for i in range(m):
  j, k = map(int, input().split())
  s[j][k] = -1
  s[k][j] = -1

Brute Force

먼저 접근한 방식은 매 케이스마다 해당 조합을 제외한 n개의 요소 중 가능한 조합을 찾아서 더하는 방식이었는데, 주어진 케이스로부터도 알 수 있듯이 불필요하게 반복을 하는 경우도 존재하게 된다.

따라서 2차원 배열을 생성해 각 숫자와 불가능한 조합을 저장해두고, 어차피 순열이 아닌 조합이므로 중첩 반복문의 index가 순차적으로 증가하도록 설정한다.

for a in range(1, n+1):
  for b in range(a+1, n+1):
    for c in range(b+1, n+1):

그리고 불가능한 조합이 아니면 count를 증가시키면 됨

...
    if s[a][b] == -1: continue
    ...
      if s[a][c] == -1 or s[b][c] == -1: continue
      ret += 1

Output

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

print(ret)