백준-9375

문제생각

• 단순히 딕셔너리로 값을 입력받은 다음 이를 조합을 이용하여 개수를 계산하면 된다고 생각하고 풀었다.

from itertools import combinations
import sys
input = sys.stdin.readline

T=int(input())
for _ in range(T):
    n=int(input())
    cloth={}
    for _ in range(n):
        name, clo=input().split()
        if clo not in cloth.keys():
            cloth[clo]=[name]
        else:
            cloth[clo].append(name)

    result=0
    for i in cloth.values():
        result+=len(i)
        
    if len(cloth.keys())!=1:
        for i in range(2, len(cloth.keys())+1):
            mul=1
            for j in combinations(cloth.values(), i):
                for k in j:
                    mul*=len(k)
                result+=mul
    print(result)

• 위의 코드는 시간초과가 난 풀이이다.

• 친구에게 힌트를 얻어 문제를 해결하였다.

• 각 옷의 종류의 값의 개수에 +1을 해준다. 이는 이 종류의 옷을 입지 않는 경우이다.

• 이 개수들을 모두 곱하여 -1을 해주면 값이 도출된다.

• 여기서 -1은 옷을 모두 입지 않는 경우이다.

import sys
input = sys.stdin.readline

T=int(input())
for _ in range(T):
    n=int(input())
    cloth={}
    for _ in range(n):
        name, clo=input().split()
        if clo not in cloth.keys():
            cloth[clo]=[name]
        else:
            cloth[clo].append(name)

    result=1
    for i in cloth.values():
        result*=(len(i)+1)
    print(result-1)