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

문제

N종류의 아이스크림 중 3가지를 고른다. M개의 조합은 함께 먹으면 안 되는 쌍이다. 금지 쌍을 포함하지 않는 3가지 조합의 수를 구하라.

입력

첫째 줄에 N, M, 이후 M줄에 금지 쌍이 주어진다.

출력

가능한 조합의 수를 출력한다.

예제

입력	출력
`5 3` `1 2` `3 4` `1 3`	`3`

풀이

모든 3가지 조합을 탐색하며 금지 쌍이 포함되지 않는 경우만 센다.

금지 쌍을 N×N 2차원 배열에 표시한다
삼중 반복문으로 모든 (i, j, k) 조합을 생성한다 (i < j < k)
세 쌍 (i,j), (i,k), (j,k) 모두 금지가 아니면 카운트를 증가시킨다

핵심 아이디어: N이 최대 200이므로 C(200,3) = 약 130만 가지로, 삼중 반복문 브루트포스가 가능하다.

코드

import sys
 
input = sys.stdin.readline
 
n, m = map(int, input().split())
ice = [[False for _ in range(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 range(n):
    for j in range(i + 1, n):
        for k in range(j + 1, n):
            if not ice[i][j] and not ice[i][k] and not ice[j][k]:
                result += 1
 
print(result)

복잡도

시간: O(N³) — 삼중 반복문
공간: O(N²) — 금지 쌍 배열

문제