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

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

풀이

• 총 N가지 아이스크림 맛이 있고, 이 중 3가지를 선택해서 조합.
• 하지만 M쌍의 조합은 같이 선택하면 안 되는 조합 (즉, 금지된 조합)이 주어짐.
• 금지된 조합이 한 쌍이라도 포함되면 해당 3개 조합은 불가능.
• 가능한 3가지 아이스크림 조합의 개수를 구해야 함.

bad = [[False] * N for _ in range(N)]

• bad[i][j]는 아이스크림 i와 j를 함께 먹을 수 없는지 여부를 저장하는 2차원 리스트.
• 인덱스는 0부터 시작하도록 처리.

for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    bad[a][b] = True
    bad[b][a] = True

• 입력으로 주어진 금지 조합을 bad 테이블에 반영 (양방향으로).

for combination in combinations(range(N), 3):

• N가지 맛 중에서 3가지를 고르는 모든 조합을 생성 (총 NC3개).

    a = combination[0]
    b = combination[1]
    c = combination[2]

    if bad[a][b] or bad[b][c] or bad[c][a]:
        continue
    answer += 1

• 현재 조합 (a, b, c) 중 금지된 쌍이 하나라도 있다면 skip.
• 모두 허용되면 가능한 조합이므로 answer 증가.

코드

# 백준 2422 - 한윤정이 이탈리아에 가서 아이스크림을 사먹는데
# 분류 : 브루트포스

from itertools import combinations

N, M = map(int, input().split())

bad = [[False] * N for _ in range(N)]
for _ in range(M) :
    a, b = map(int, input().split())
    a -= 1
    b -= 1

    bad[a][b] = True
    bad[b][a] = True

answer = 0
for combination in combinations(range(N), 3) :
    a = combination[0]
    b = combination[1]
    c = combination[2]

    if bad[a][b] or bad[b][c] or bad[c][a] :
        continue
    answer += 1

print(answer)