[백 준/구현] 9375: 패션왕 신해빈

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

9375번: 패션왕 신해빈

핵심 아이디어

• dictionary
• Counter class 활용(파이썬)

같은 종류의 의상은 하나씩만 착용할 수 있으며, 알몸이 아니어야 하므로 꼭 1종류 이상의 의상은 착용해야 한다.

예를 들어, 3종류의 의상이 있으면 1종류만 착용해도 되며, 2종류를 착용해도 되고, 3종류를 착용해도 되지만

0종류를 착용하는건 안된다. 그렇다면 다음과 같은 식을 세울 수 있습니다.

• (a종류수 + 1) * (b종류수 + 1) * (c종류수 + 1)... - 1

여기서 종류수에 +1을 해준 이유는 그 종류의 의상을 착용해도 되고 안해도 되기 때문이고 마지막에 -1을 해준 이유는 모든 의상을 착용하지 않은 경우를 제외시켜줘야 하기 때문입니다.

풀이

아래의 풀이는 파이썬의 Counter모듈을 이용하여 딕셔너리를 직접 제작하지 않아도 자동으로 개수를 세주는 기능을 이용하였습니다.

from collections import Counter
import sys
input = sys.stdin.readline

t = int(input())

for _ in range(t):
	n = int(input())
	wear = []
	for i in range(n):
		a, b = input().split()
		wear.append(b)
	wear_Counter = Counter(wear)
	#print(wear_Counter)
	count = 1 # 각 종류마다 항목의 개수

	for j in wear_Counter:
		count *= wear_Counter[j] + 1
	print(count - 1)

아래는 파이썬의 딕셔너리를 제작해서 풀이하였습니다.

import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	wear_dic = {}
	for i in range(n):
		wear = list(input().split())
		if wear[1] in wear_dic:
			wear_dic[wear[1]].append(wear[0])
		else:
			wear_dic[wear[1]] = [wear[0]]
	count = 1
	for k in wear_dic:
		#print(k) headgear, eyewear
		count *= (len(wear_dic[k]) + 1)
	print(count - 1)