[백준 알고리즘]패션왕 신해빈(9375)

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

이 문제의 경우 간단한 방법을 이용해서 조합을 구현하지 않아도 해결할 수 있는 문제입니다.

각 의상의 종류마다 n1, n2, n3, ...가지를 가지고 있다면 의상을 입지 않는 경우를 포함하여 경우의 수를 계산할 수 있습니다.

$$_{n_{1}+1}C_{1}\times _{n_{2}+1}C_{1}\times _{n_{3}+1}C_{1}\times ...$$

여기서 모든 종류의 의상을 입지 않는 경우 한 가지만 빼면 모든 경우의 수를 구할 수 있습니다.

따라서 코드로 구현해야할 식을 다음과 같습니다.

$$(n_{1}+1)\times (n_{2}+1)\times (n_{3}+1)\times ... - 1$$

파이썬 코드로 구현해보겠습니다.

n = int(input())
items = {} // 의상종류를 키값으로 하는 딕셔너리 변수 생성
for i in range(n):
    item, gear = input().split()
    if not gear in items: // 새로운 의상종류를 추가
        items[gear] = []
    items[gear].append(item)

의상을 종류별로 정리하기 위해 딕셔너리 자료형을 이용했습니다.

새로운 의상종류일 경우 딕셔너리 자료형에 새로운 키를 추가하며 이미 존재한다면 어떤 의상인지 밸류값을 리스트로 구성하여 추가하도록 했습니다.

sum = 1
for i in items:
    sum *= len(items[i]) + 1
sum -= 1

종류별로 정렬된 의상들의 개수를 이용하여 결과값을 구하는 코드입니다.

case = int(input())
for i in range(case):
    n = int(input())
    items = {}
    for i in range(n):
        item, gear = input().split()
        if not gear in items:
            items[gear] = []
        items[gear].append(item)

    sum = 1
    for i in items:
        sum *= len(items[i]) + 1

    sum -= 1
    print(sum)