[Python] 백준 9375번: 패션왕 신해빈

풀이 전략은 다음과 같습니다.

문제의 핵심은 "같은 종류의 의상은 하나만 입을 수 있다" 인데요!
의상 종류별로 아래의 2가지 상황이 있을 수 있습니다.

1. 해당 종류의 의상을 아무것도 입지 않은 경우
2. 해당 종류의 의상 중 하나를 선택하여 입은 경우

이런 종류의 문제, 확률과 통계에서 자주 만났던 유형이죠?

A 종류의 의상이 a개, B 종류의 의상이 b개 있을 때
A 종류의 의상 중 1개, B 종류의 의상 중 1개를 선택하는 경우의 수는 아래와 같았습니다.

a * b

여기에 A 종류의 의상을 아무것도 입지 않은 경우와 B 종류의 의상을 아무것도 입지 않은 경우를 포함하고, 알몸인 상황을 제외해주면 경우의 수는 아래와 같습니다.

( a + 1 ) * ( b + 1 ) - 1

따라서 위의 공식을 편리하게 적용하려면 의상 종류별 개수를 알아야 합니다.

이는 Python의 dictionary, 즉 맵 자료구조를 이용하여
의상 종류의 이름을 key로, 종류의 개수를 value로 저장하면 문제를 쉽게 풀 수 있습니다.

코드를 보면 clothes_list [ type ] 을 2로 초기화한 것을 알 수 있는데요!
이는 선택한 종류의 의상을 아무것도 입지 않은 상황을 포함했기 때문입니다.

마지막에 cnt - 1을 해주어 맨몸인 상황을 제외해주었습니다.

import sys

T = int(sys.stdin.readline())
ans = ""

for _ in range(T):
    N = int(sys.stdin.readline())
    clothes_list = {}
    cnt = 1
    for i in range(N):
        _, type = sys.stdin.readline().split()
        #  의상 종류별 개수를 저장
        if type in clothes_list.keys():
            clothes_list[type] = clothes_list[type] + 1
        else:
            clothes_list[type] = 2

    for c in clothes_list.values():
        cnt *= c
    ans += str(cnt - 1) + '\n' # 맨몸인 상황을 제외

print(ans)

선택한 종류의 의상을 아무것도 입지 않은 상황을 포함하여 계산하는 것이
중요했던 문제로 보여집니다.