[백준] 9375 패션왕 신해빈

백준 9375 패션왕 신해빈

문제 이해하기

1. 옷의 종류(상의, 하의, 신발 등)와 각 종류에 대한 옷(맨투맨, 후드, 청바지, 운동화 등)이 각각 주어진다.
2. 주어진 옷들을 가지고 최소한 1가지는 입고 있을 수 있도록함(알몸은 안됨)과 동시에 같은 종류의 옷이 아닌(ex. 맨투맨과 후드는 둘 다 "상의"에 해당하기 때문에 같이 입을 수 없음) 경우의 수를 모두 센다.

 

옷의 종류 수를 n이라고 했을때, 위의 조건을 가지고 아래와 같은 식을 도출할 수 있다.
((옷 종류1에 있는 옷의 개수 + 1) * (옷 종류2에 있는 옷의 개수 + 1) * ... * (옷 종류n에 있는 옷의 개수 + 1)) - 1

 

여기서 각 옷 종류에 있는 옷의 개수에 + 1을 해주는 이유는 해당 종류의 옷을 입지 않는 경우도 있기 때문이다.

 

예를들어, 문제에 주어진 예제처럼 모자에 해당하는 항목에 hat, turban이 있다고 가정하면

• hat을 입는 경우
• turban을 입는 경우
• 둘 다 입지 않는 경우

 

이렇게 3가지가 있기 때문에 각 옷 종류에 있는 옷의 개수에 1을 더해주는 것이다.

 

또한, 마지막에 -1을 해주는 이유는 매 종류마다 +1을 함으로써 모든 옷을 입지 않는 경우의 수가 이미 계산되었기 때문에 이에 대한 경우를 제외해야하기 때문이다.

 

풀이

import sys
input=sys.stdin.readline

T=int(input())

for _ in range(T):
  n=int(input())
  if n==0:
    print(0)
    continue

  clothes={}
  for _ in range(n):
    costume,costumeType=map(str, input().split())

    if costumeType not in clothes:
      clothes[costumeType]=[costume]
    else:
      clothes[costumeType].append(costume)

  possibleCase=1
  for key in clothes:
    possibleCase*=len(clothes[key])+1

  print(possibleCase-1)

 

알게 된 점

파이썬해서 딕셔너리를 통한 해시맵을 구현하는데 value로 리스트를 집어넣을수도 있다는 것을 알게 되었다.
어떤 키-값 쌍을 추가할때 해당 키가 이미 딕셔너리에 있는지 검사하여 없다면 clothes[costumeType]=[costume]와 같은 형태로 리스트 value를 생성해줄 수 있고, 그 이후부터는 clothes[costumeType].append(costume)와 같이 append를 통해서 value를 추가해줄수 있다.

 

그러면 아래와 같이 딕셔너리가 생성된다.

{'headgear': ['hat', 'turban'], 'eyewear': ['sunglasses']}