9375번 패션왕 신해빈

문제링크 : www.acmicpc.net/problem/9375

9375번: 패션왕 신해빈

 

<문제 풀이 방법>

ex )   예제                                              종류별로 구분

        3                                                  headgear   2

        hat headgear                                  eyewear    1

        sunglassess eyewear                      

        turban headgear 

 

종류별로 고려한 경우 : 2C1+2C2

종류 + 종류별 개수 고려한 경우 : 2C1*2+2C1*1+2C2*(2*1) = 2*2+2*1+2*+2 = 5

 

 => headgeaer -> headgear1, headgear2, no headgear

      eyewear -> eyewear1, no eyewear

      로 종류 구분을 하고 서로 짝지어 본후, no headgear와 no eyewear 끼리 짝지어진 경우를 뺀다.

 

 

 

<알고리즘>

  1) 입력받은 물건들을 종류별로 카운팅

  2) 종류별 갯수+1을 모두 곱한후 -1

import sys
from collections import Counter
T = int(sys.stdin.readline())
for _ in range(T):
    N = int(sys.stdin.readline())
    item = []
    for i in range(N):
        name, kind = sys.stdin.readline().split()
        item.append(kind)
    sortItem = Counter(item)
    result =1
    for i in sortItem:
        result*=(sortItem[i]+1)
    print(result-1)

 

+) Counter 함수 사용 : www.daleseo.com/python-collections-counter/

[파이썬] collections 모듈의 Counter 클래스 사용법