백준 2422번: 한윤정이 이탈리아에 가서 아이스크림을 사먹는데 (S4) - Python 풀이

문제 설명

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

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

입력

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

출력

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

예제 입력 1

5 3
1 2
3 4
1 3

예제 출력 1

3

힌트

5개의 아이스크림과 3가지 섞어먹으면 안 되는 조합이 있다. 1번은 2번 3번과 섞으면 안되고, 3번은 4번과 섞으면 안 된다. 따라서 (1 4 5), (2 3 5), (2 4 5)와 같이 3가지 방법이 있다.

문제 요약) 아이스크림 3가지 선택할 때 최악의 조합을 제외하면 총 경우의 수가 몇 개인가?

풀이 과정

문제가 딱 봐도 조합의 느낌이 듭니다.

파이썬 itertools의 combinations 함수를 써서 N개의 아이스크림 중 3가지를 고르는 모든 경우의 수를 구합니다.

처음에는 전체 조합에서 최악의 조합이 포함된 것의 개수를 구하고, 전체 경우의 수에서 빼주는 방식을 했는데 이 경우 시간 초과가 발생했습니다. itertools.combinations 자체도 시간 복잡도가 큰데, 그 안에서 또 for문으로 최악의 조합을 하나씩 확인하다 보니 발생하는 문제였습니다. combinations는 O(nCr)의 시간 복잡도를 가집니다. 이 문제의 경우 n은 최대 200, r=3으로 고정이라서 최악일 때 시간 복잡도가 O(200C3) = 약 130만이라 괜찮은 것 같습니다. itertools를 쓰는 순간 웬만해서 내부 연산은 O(1)에서 돌아가도록 짜야 합니다.

그래서 Bool 타입의 2차원 배열을 만들고 어떤 조합이 최악인지를 저장했습니다. 하나의 for문으로 전체 경우의 수를 돌면서 해당 경우가 최악인지 아닌지의 여부만 확인하도록 구현했습니다.

정답 코드

import itertools

# 아이스크림의 개수와 최악 조합의 개수
N, M = map(int, input().split())
ice_creams = [i for i in range(1, N+1)]
# 최악의 쌍인지 여부를 저장할 Bool 타입 2차원 배열
is_deleted_comb = [[False] * (N+1) for _ in range(N+1)]

# M개의 최악의 쌍을 입력
for _ in range(M):
    a, b = map(int, input().split())
    # a와 b는 함께 선택할 수 없다
    is_deleted_comb[a][b] = True
    # 양방향으로 표시해 주어야 합니다
    is_deleted_comb[b][a] = True

count = 0
# 아이스크림 N개에서 3개를 선택하는 전체 조합 구하기
for a, b, c in itertools.combinations(ice_creams, 3):
    # a와 b가 함께할 수 있나요? / b와 c가 함께할 수 있나요? / a와 c가 함께할 수 있나요? 를 인덱스만으로 확인
    if is_deleted_comb[a][b] or is_deleted_comb[b][c] or is_deleted_comb[a][c]:
        # 최악이면 카운트 안 하고 다음 턴
        continue
    # 함께할 수 있다면 카운트 누적
    count += 1

print(count)

2차원 배열에 인덱스로 불가능한 조합을 저장함으로써 combinations를 하나씩 확인하는 for문에서도 a, b, c의 인덱스 접근만으로 최악인지 아닌지를 판별할 수 있었습니다.

특히 최악의 쌍의 입력이 꼭 1 3 이렇게 오름차순으로 들어온다는 보장이 없기 때문에(3 1 이렇게 들어올 수도 있음) itertools.combinations()은 항상 오름차순으로 조합을 생성하더라도 is_deleted_comb[a][b] = True와 is_deleted_comb[b][a] = True을 모두 해줌으로써 양방향으로 안 되는 조합을 저장해 두어야 합니다.

이상입니다.