[Hash] 백준 9375번 “패션왕 신해빈” Python 풀이

문제 링크

• https://www.acmicpc.net/problem/9375

풀이

• 참고
  • 의상을 한 개만 걸치고 있어도 알몸이 아닙니다.
  • 같은 종류의 의상은 하나만 입을 수 있습니다.
  • 주어진 의상으로 만들 수 있는 조합의 개수가 정답이 됩니다.
• 따라서, 주어진 의상에 대한 조합의 개수는 아래와 같이 계산할 수 있습니다.
  • ( a 의상의 종류 수 + 1 ) * ( b 의상의 종류 수 + 1 ) * ( c 의상의 종류 수 + 1 ) … -1
• 각 의상의 종류 수에 +1을 해준 이유는, 해당 의상을 착용하지 않는 경우도 포함하기 위함입니다.
• 마지막에 -1을 해준 이유는, 모든 의상을 착용하지 않은 경우는 제외하기 위함입니다.

코드

import sys

t = int(sys.stdin.readline())

for _ in range(t):

    dict = {}

    n = int(sys.stdin.readline())

    for _ in range(n):

        # 의상의 이름과 종류 입력
        name, category = sys.stdin.readline().split()

        # 딕셔너리에 해당 의상 종류가 존재할 경우
        if (category in dict):
            dict[category] += 1
        # 딕셔너리에 해당 의상 종류가 존재하지 않을 경우
        else:
            dict[category] = 1

    # 의상 종류에 따른 조합의 개수 계산
    result = 1
    for count in dict.values():
        result *= count + 1
    result -= 1

    print(result)