[파이썬 | BOJ | 9375] 패션왕 신해빈

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

9375번: 패션왕 신해빈

문제

해빈이는 패션에 매우 민감해서 한번 입었던 옷들의 조합을 절대 다시 입지 않는다. 예를 들어 오늘 해빈이가 안경, 코트, 상의, 신발을 입었다면, 다음날은 바지를 추가로 입거나 안경대신 렌즈를 착용하거나 해야한다. 해빈이가 가진 의상들이 주어졌을때 과연 해빈이는 알몸이 아닌 상태로 며칠동안 밖에 돌아다닐 수 있을까?

입력

첫째 줄에 테스트 케이스가 주어진다. 테스트 케이스는 최대 100이다.

• 각 테스트 케이스의 첫째 줄에는 해빈이가 가진 의상의 수 n(0 ≤ n ≤ 30)이 주어진다.
• 다음 n개에는 해빈이가 가진 의상의 이름과 의상의 종류가 공백으로 구분되어 주어진다. 같은 종류의 의상은 하나만 입을 수 있다.

모든 문자열은 1이상 20이하의 알파벳 소문자로 이루어져있으며 같은 이름을 가진 의상은 존재하지 않는다.

출력

각 테스트 케이스에 대해 해빈이가 알몸이 아닌 상태로 의상을 입을 수 있는 경우를 출력하시오.

풀이

이 문제의 까다로운 점은 의상의 종류 이름이 문자열로 무제한으로 주어질 수 있다는 점이다.

 

따라서 일단 의상의 문자열이 들어오면, 그 의상이 한번도 나온 적이 없으면 문자열로 넣고 check배열의 index를 늘려서 표시하고, 의상이 한번이라도 나온적이 있으면 그 의상의 인덱스에 해당하는 check배열의 값을 늘리는 식으로 구성했다.

 

그리고 나서 처음에는 의상의 종류가 K개라면 2^K-1개에 해당하는 경우의 수를 모두 탐색한 뒤, 각 경우에 해당하는 경우의 수를 모두 더한다. 예를들어 의상1 의상2이 있고 각 의상마다 2개, 3개가 있다면 [O, O] = 6, [O, X] = 2, [X, O] = 3이므로 총 11개의 경우의 수가 있다.

 

따라서 2^K-1개의 경우의 수를 재귀적으로 탐색하여서 모든 경우의 수를 더했더니 시간초과가 떴다.

 

하지만 위의 경우의 수를 수학적으로 간단히 해결 할 수가 있는데, 의상1에 해당하는 의상의 경우가 총 3개(사용안함, 의상1-1, 의상1-2)이고 의상2에 해당하는 의상의 경우가 총 4개(사용안함, 의상2-1, 의상2-2, 의상2-3)인데, 둘다 사용안함이면 안되므로 3 * 4 - 1로 간단히 계산할 수 있다.

 

따라서 모든 의상의 경우의 수에 + 1 한 값을 모두 곱해서 - 1 을 하면 답이 된다.

 

 

# [파이썬 | BOJ | 9375] 패션왕 신해빈
 
import sys
read = sys.stdin.readline
 
T = int(read())
 
for _ in range(T):
    ans = 0
    check = [1 for _ in range(31)]
    
    N = int(read())
    temp = []
    cnt = -1
    for _ in range(N):
        a, b = map(str, read().split())
        if not b in temp:
            temp.append(b)
            cnt += 1
            check[cnt] += 1
        else:
            check[temp.index(b)] += 1
    M = len(temp)
 
    t = 1
 
    for i in range(check.index(1)):
        t *= check[i]
    print(t-1)