패션왕 신해빈

import sys 
input = sys.stdin.readline

def BOJ9375() :
  T = int(input())
  for _ in range(T) :
    n = int(input())
    dict = {}
    for _ in range(n) :
      _, type = input().split()
      if type in dict :
        dict[type] += 1
      else :
        dict[type] = 1
    
    answer = 1
    
    for i in dict.values() :
      answer *= (i+1)
    print(answer - 1)

BOJ9375()

 

접근방법 :

1. 옷의 이름은 필요 없다. 입을지 말지 무엇을 입을지만 알고싶다.

2. 타입은 두개 옷의 종류는 각각 3개, 2개라 가정해보자, 아래의 이미지에 표현해두었다.

타입별로 선택하지 않는 옵션의 가지수를 추가한다. 

그러면 4개, 3개가 된다.

4개중 하나를 선택하는 경우와 3개중 하나를 선택하는 경우를 곱해준다.

그 이후 선택x, 선택x를 동시에 선택한 경우의수 1가지를 빼면 답에 접근할 수 있다

 

4 * 3 - 1 = 11

 

 

장애물 이였던 것 :

1. 학창시절에도 경우의 수 문제는 너무 어려웠다. 처음 시도한 방법은 메모리가 초과해서 실패했고 경우의 수 관련 다른 분들의 풀이를 참고했다.

 

 

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

9375번: 패션왕 신해빈