[BOJ] 9375번: 패션왕 신해빈

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

9375번: 패션왕 신해빈

 

 

1. 문제 설명 

혜빈이는 한번 입었던 옷들의 조합은 절대 다시 입지 않는다. 옷을 입을 때 주어진 옷의 종류를 모두 입지 않아도 된다. (안경, 반팔, 반바지가 주어지면 안경과 반팔만 입는 경우, 반팔과 반바지만 입는 경우도 존재한다.) 알몸인 상태만 되지 않으면 된다. 

 

 

 

2. 접근 방식 

조합으로 접근했는데 옷을 안입는 경우와 옷을 모두 입지 않은 경우에 대한 처리를 제대로 해주지 못했다. 

 

ex ) headwear (4), eyewear(2), shoes(3) 

 

(headwear를 입는 경우 (4)  + headwear를 입지 않는 경우 (1)) + (eyewear를 입는 경우 (2)  + eyewear를 입지 않는 경우 (1)) + (shoes를 입는 경우 (3)  + shoes를 입지 않는 경우 (1)) - 모든 옷을 입지 않는 경우(1)

 

=> ((4 + 1) + (2 + 1) + (3 + 1)) - 1 

 

각 의상 타입에 대해서 옷을 입지 않는 경우를 각각 1씩 더해줬으므로 모든 옷을 입지 않는 경우 1을 빼줘야한다.(알몸이 되면 안되기 때문에)

 

 

 

3. 주석 달기 (변수 설명, 각 줄마다 문장으로 설명, 함수 설명)

import sys
from collections import defaultdict
input = sys.stdin.readline
T = int(input())
for _ in range(T):
    ans = 1
    n = int(input())
    dic = defaultdict(int)
    for _ in range(n):
        name, type = input().split()
        dic[type] += 1

    for k in dic.values():
        ans *= (k + 1)
    print(ans-1)

4. 분석 및 시간복잡도 

시간복잡도 : O(N)