패션왕 신해빈

문제

내가 푼 풀이

import sys
from itertools import combinations
for test_case in range(1):
    n = int(sys.stdin.readline())

    for _ in range(n):
        cnt = int(sys.stdin.readline())
        dp = {}

        for _ in range(cnt):
            name, type = sys.stdin.readline().split()

            if type not in dp:
                dp[type] = [name]
            else:
                dp[type] += [name]

        types = list(dp.keys())
        arr = []
        for type in types:
            arr.append(len(dp[type]))

        ans = 0
        for i in range(1, len(types) + 1):
            cases = list(combinations(arr, i))

            for case in cases:
                total = 1
                for c in case:
                    total *= c
                ans += total

        print(ans)

Combination을 사용해 풀었다.
만약 headgear의 개수가 3, face의 개수가 2, eyewear = 1이라고 가정하자
그럼 arr = [3, 2, 1]이 될 것이고 이것을 컴비네이션으로 풀게 되면
i = 1일 때 => 3, 2, 1
i = 2일 때 => 3*2, 3*1, 2*1
i = 3일 때 => 3*2*1
총 합을 구하면 23이 된다. 하지만 이렇게 하면 메모리 초과가 발생한다.

수학적으로 접근

for test_case in range(1):
    n = int(sys.stdin.readline())

    for _ in range(n):
        cnt = int(sys.stdin.readline())
        dp = {}

        for _ in range(cnt):
            name, type = sys.stdin.readline().split()

            if type not in dp:
                dp[type] = [name]
            else:
                dp[type] += [name]

        types = list(dp.keys())
        arr = []
        for type in types:
            arr.append(len(dp[type]))

        ans = 1

        for num in arr:
            ans *= num + 1
        print(ans - 1)

arr =[3, 2, 1]일 때 조합으로 일일히 구하지 말고
경우의 수를 생각해보자
3일 때 첫번째, 두번째, 세번째, 아무것도 선택안할 때 => 4
2일 때 첫번째, 두번째, 아무것도 선택 안할때 =>3
1일 때 첫번째, 아무것도 선택 안할때=>2
모든 경우의 수는 4*3*2가 된다.
여기서 아무것도 선택안할 때인 1을 빼주면 23이 된다.