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

 

# 한번 입었던 조합은 안됨 = 중복 안됨
# 의상의 분류와 의상들이 주어졌을때 중복 없이 만들 수 있는 조합의 수
# 옷의 종류별로 분류. 각 종류에 대해 (해당 종류의 옷 개수 + 안입는 경우(1))을 종류만큼 곱해주고 아무것도 안입는 알몸인 경우 1가지를 빼준다
import sys
case = int(input())
for _ in range(case): # 케이스만큼 반복
    n = int(input()) # 의상 수
    clothes = {}
    for _ in range(n):
        name, type = sys.stdin.readline().rstrip().split()

        if type in clothes: # 의상의 종류별 총 개수를 딕셔너리에 저장
            clothes[type] += 1
        else:
            clothes[type] = 1
    result = 1 # 곱셈을 해야하니 초기값으로 1을 줌 
    for i in clothes:
        result *= (clothes[i] + 1) # 의상 종류의 총 개수 + 의상을 안입는 경우를 종류만큼 곱함
    print(result - 1) # 알몸인 경우를 뺌

 

처음에는 해시 테이블 자료구조를 사용해야 하니까 각 key의 value로 리스트가 들어가고 거기서 각각 반복문을 사용해서 구현해야하나? 라고 생각했었다. 하지만 그렇게 하니까 풀리지 않았고 검색을 해서 알아보니 그냥 경우의 수를 사용하는 문제였다. 

주어진 테스트 케이스만큼 반복하고 입력되는 의상의 종류에 따라서 딕셔너리 clothes에 없을 경우 key 값으로 등록하고 기본값을 주고, 만약 있다면 value를 1씩 증가시킨다. 

옷의 종류별로 해당 종류의 옷 개수 + 안입는 경우(1)를 구하고 모두 곱한 값에 아무것도 입지 않는 경우(1)을 빼주면 결과값이 나온다. 

예시의 첫번째 테스트 케이스로 해본다면 headgear : 옷 개수 2 + 아무것도 안하는 경우 1 X eyewear : 옷 개수 1 + 안하는 경우 1 => (2 + 1) X (1 + 1) = 6이 된다. 그리고 여기에서 해빈이가 아무것도 입지 않는 경우는 없으므로, 아무것도 안입는 경우인 1을 빼준다. 6 - 1 = 5. 그래서 결과는 5가 된다. 좀 헷갈렸지만 결국은 그냥 수학 문제였다... 🥲

 

 

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

9375번: 패션왕 신해빈