백준 9375 - 패션왕 신해빈 (파이썬)

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

풀이

이 문제는 조합을 활용하여 해결 할 수 있는 문제이다.

주어진 의상의 종류별로 착용할 수 있는 경우의 수를 계산하여 모든 조합을 구하는 방식이다.

쉽게 설명하기 위해서, 예시를 바탕으로 분석을 진행한다.

2
3
hat headgear
sunglasses eyewear
turban headgear
3
mask face
sunglasses face
makeup face

1. 첫 번째 테스트 케이스

count = {
    "headgear": 2,
    "eyewear": 1
}

경우의 수 : (2 + 1) * (1 + 1) - 1 = 5

1. 두 번째 테스트 케이스

count = {
    "face": 3
}

경우의 수: (3+1) - 1 = 3

시간 복잡도 분석

• N개의 의상을 입력받고 딕셔너리를 사용하여 저장하는 데 O(N).
• 경우의 수를 계산하는 과정에서 O(K) (K는 의상의 종류 수).
• 총 테스트 케이스가 T개 있으므로 O(T * (N + K)).

즉, 최대 약 O(TN)의 시간 복잡도를 가지므로 효율적

코드

# 백준 9375 - 패션왕 신빈
# 분류 : 조합

T = int(input())

for _ in range(T) :
    count = {}
    N = int(input())
    for _ in range(N) :
        _, t = input().split()

        if t not in count :
            count[t] = 0
        count[t] += 1
    
    answer = 1
    for k, v in count.items() :
        answer *= (v + 1)
    answer -= 1
    print(answer)