[백준] 9375번 (python 파이썬)

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

 

조합을 구하는 문제이다.

하지만 같은 종류의 옷은 동시에 입을 수 없다.

즉, 같은 종류의 옷들을 묶은다음 해당 종류별로 경우의 수를 곱해주면 된다.

 

만약

hat headgear

sunglasses eyewear

turban headgear

가 있다면

headgear : 2개

eyewear : 1개이다.

(dict을 이용하면 된다.)

이러면

headgear을 고를 경우의 수 ( 2 + 1 (hat, turban, 아무것도 안고를 경우))

eyewaer을 고를 경우의 수 ( 1 + 1 (sunglasses, 아무것도 안고를 경우))

= 6인데 문제에서 아무것도 안입으면 안되기 때문에 여기서 아무것도 안입는 경우 1을 빼준다.

6-1이 답이다.

 

처음에는 파이썬의 combination을 사용하여 풀었지만 메모리 초과가 나왔다... 

 

case = int(input())

for _ in range(case):
    n = int(input())
    items = list(input() for _ in range(n))
    items_dict = dict()
    for i in range(len(items)):
        if items[i].split()[1] in items_dict:
            items_dict[items[i].split()[1]] += 1
        else:
            items_dict[items[i].split()[1]] = 1
    items = list(items_dict.values())
    total = 1

    for i in items:
        total *= (i + 1)
    print(total-1)