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

문제

해설

처음에 모든 경우의 수를 검사하는 코드를 작성했는데, 시간초과가 난 문제이다.

모든 경우의 수를 검사하지 말고

각 의상의 종류에 아무것도 입지 않을 경우 1을 더하고,

각 의상의 종류 가짓수를 곱해주고, 아무것도 입지 않을 경우 1을 빼준다.

코드

import sys
input = sys.stdin.readline

def main():
    for _ in range(int(input().strip())):
        dic = {}
        ans = 1
        for _ in range(int(input().strip())):
            _, t = map(str, input().split())
            dic[t] = dic[t] + 1 if t in dic else 2
        for i in dic:
            ans *= dic[i]
        print(ans - 1)

if __name__ == "__main__":
    main()