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

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

 

[초기 접근 방법(X)]

1. 주어진 아이스크림에서 3가지 조합을 모두 구한다.

2. 모든 조합 경우에서, 금지된 조합(x, y)가 포함될 시 총 count(nC3)에서 -1을 한다.

3. 가능한 조합 count를 출력한다.

 

[생각]

위 접근 방법대로 풀면 시간복잡도가 O(M * nC3)이다. (M : 금지된 조합, N : 아이스크림 갯수)

금지된 조합에 대해 (x, y) (y, x) 에 대한 boolean 처리를 해주고,

nC3 조합에 대해 금지된 조합이 있는지 여부를 판단하는 것이 효율적이다..

*어려운 문제는 아니였지만, 시간복잡도의 최적화에 대해서 고민한 문제였다.

 

[코드]

# 풀이 시간 : 20분 + 10분
# 시간복잡도 : O(nC3)
# 공간복잡도 : O(N or M)
# 참고 : https://changsroad.tistory.com/133

import itertools
import sys
input = sys.stdin.readline

# N : 아이스크림 종류의 수, M : 섞어먹으면 안 되는 조합의 개수
N, M = map(int, input().split())

# 금지된 조합
exhibit = [[False] * N for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    exhibit[a-1][b-1] = True
    exhibit[b-1][a-1] = True

count = 0
for i in itertools.combinations(range(N), 3):
    # i : 3가지 아이스크림 맛
    # 3쌍 중에 1가지라도 금지된 조합이 있을 시
        # 해당 맛 조합은 채용해서는 안된다.
    if exhibit[i[0]][i[1]] or exhibit[i[1]][i[2]] or exhibit[i[2]][i[0]]:
        continue

    count += 1

print(count)