[백준/파이썬] 9375번: 패션왕 신해빈

문제

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

풀이

주어진 의상을 가지고 몇 가지 조합이 나오는지 구하는 문제

딕셔너리를 이용해 의상의 종류와 의상 이름을 저장해 조합을 구하면 됩니다.

wear = dict() # 의상 정보를 저장할 딕셔너리 선언
for _ in range(int(input())): # 의상 개수
	a,b = input().split() # 의상 이름, 종류
    if b in wear: # 딕셔너리 안에 옷의 종류가 이미 저장되어 있으면
    	wear[b].append(a) # 의상 이름 추가
    else: # 딕셔너리 안에 입력한 종류가 없으면
    	wear[b] = [a] # (의상 종류: 이름) 추가

여기까지는 금방 했는데 조합을 어떻게 구할지 굉장히 막막했습니다.
$nCr$을 이용해 구해야 하나? 싶어 구글링을 해봤는데, 조합 알고리즘을 이용하면 굉장히 쉽게 구할 수 있겠더군요.

만약 headgear에 해당하는 의상 [hat, turban], face에 해당하는 의상 [mask, sunglasses, makeup]이 있을 때
나올 수 있는 조합은 headgear에 해당하는 의상 착용했을 때와 안 했을 때(hat, turban, x)와 face에 해당하는 의상을 착용했을 때와 안 했을 때(mask, sunglasses, makeup, x)가 있습니다.

조합

hat
turban
mask
sunglasses
makeup
hat, mask
hat, sunglasses
hat, makeup
turban, mask
turban, sunglasses
turban, makeup
x

즉, (headgear의 종류 2가지 + 착용 안 했을 경우) + (face의 종류 3가지 + 착용 안 했을 경우) = 3*4 = 12가지가 나오게 됩니다.

문제에서 알몸이 아닌 상태는 제외해야 된다고 해서 총 가지수에서 -1을 해주면 됩니다.

코드

import sys
input = sys.stdin.readline

for _ in range(int(input())): # 테스트 케이스
    wear = dict()
    for _ in range(int(input())):
        a, b = input().split()
        if b in wear:
            wear[b].append(a)
        else:
            wear[b] = [a]
    
    cnt = 1
    for i in wear:
        cnt *= len(wear[i]) + 1
    print(cnt -1)