(BOJ) 제9375호: 패션왕 신해빈

원천: https://www.acmicpc.net/problem/9375

1. 문제를 설명하십시오

혜빈은 자신이 입어본 옷을 조합해서 입어본 적이 없다. 옷을 입을 때 주어진 모든 종류의 옷을 입을 필요는 없습니다. (안경, 반팔, 반바지를 주면 안경과 반팔만 입는 경우도 있고, 반팔과 반바지만 입는 경우도 있습니다.) 알몸이 아닌 이상.

2. 방법

구성으로 접근하고 있는데, 옷이 없는 경우와 옷을 다 안 입고 있는 경우를 알 수 없습니다.

ex) 헤드기어(4), 안경(2), 신발(3)

(모자 착용 시 (4) + 미착용 시 (1)) + (안경 착용 시 (2) + 미착용 시 (1)) + (신발 착용 시 (3) + 미착용 시 (1)) – 옷을 입지 않은 경우(1)

=> ((4 + 1) + (2 + 1) + (3 + 1)) – 1

각 유형의 옷에 대해 옷이 없는 경우마다 1을 더하므로 옷이 없는 경우 1을 빼야 합니다(알몸이 되고 싶지 않기 때문).

3. 주석(변수 설명, 각 줄을 한 문장으로 설명, 함수 설명)

import sys
from collections import defaultdict
input = sys.stdin.readline
T = int(input())
for _ in range(T):
    ans = 1
    n = int(input())
    dic = defaultdict(int)
    for _ in range(n):
        name, type = input().split()
        dic(type) += 1

    for k in dic.values():
        ans *= (k + 1)
    print(ans-1)

4. 분석 및 시간 복잡도

시간 복잡도: O(N)