[백준알고리즘] 9375번: 패션왕 신해빈 -Python

[백준알고리즘] 9375번: 패션왕 신해빈 -Python

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

9375번: 패션왕 신해빈

 

이 문제는 공식만 찾으면 바로 풀 수 있는 문제라고 생각한다.

 

처음에 무슨 옷을 입는지는 중요하지 않다는 것을 알았다. 옷의 종류가 중요한 것이다. 옷 종류별로 옷의 개수만 파악하고 있도록 했다.

 

이유는 조합을 사용해서 생각을 했기 때문인데, 첫번째 테스트 케이스를 보도록 하자.

hat headgear

sunglasses eyewear

turban headgear

이렇게 3가지가 있을 때, headgear중 하나를 입을 수 있으니 2C1, eyewear 중 하나를 착용할 수 있으니 1C1이라고 생각을 했다.

 

그러고 나서는 headgear만 착용할 때, eyewear만 착용할 때, headgear와 eyegear를 모두 착용할 때 가능한 경우의 수를 따졌었다. 그러면 2C1 + 1C1 + 2C1*1C1의 식이 된다.

 

 

이런 식으로 생각을 하니 코드를 구성할 때 만약 옷의 종류가 5개라면 그중 3개의 옷의 종류를 선택하고 거기서 저장된 옷의 개수를 읽어와서 곱하는 경우의 수들이 무지하게 많았다. 5개가 아니라 30개라면? 시간 초과가 발생할 것 같았다.

예를 들자면 30개의 옷 종료중 15개를 선택해야 하며 선택된 옷의 개수들을 곱해서 반복적으로 더해줘야 하는데, 이 30개에서 15개를 정하는 모든 방법들이 for문을 무지막지하게 돌기 때문이다.

 

 

그러다가 다시 시야를 넓게봤더니 금방 해결이 됐다. 다시 첫 번째 테스트 케이스를 보도록 하자.

hat headgear

sunglasses eyewear

turban headgear

이렇게 있을 때 처음에는 headgear가 2개 eyewear가 1개라고 생각을 했는데, 안 입는 경우도 각각 포함시키도록 하면 된다. 그러니까 headgear에 대해서는 3가지 방법이 있는 것이다. 1. hat을 착용하는 방법 2. turban을 착용하는 방법 3. 착용하지 않는 방법. 마찬가지로 eyewear도 적용을 한다. 1. sungalsses를 착용하는 방법, 2. 착용하지 않는 방법.

 

이렇게 하면 headgear와 eyewear를 착용하거나 착용하지 않는 경우의 수는 (3*2)가 된다.

하지만 여기서 headgear를 착용하지 않고, eyewear도 착용하지 않는 여기서 말하는 알몸인 경우가 1개 존재하기 때문에 그 경우를 빼준다면 (3*2-1)이 된다.

 

 

따라서 새롭게 식으로 나타내면, 각 옷의 종류가 A~Z까지 있고, 각 옷의 종류별 개수를 a~z라고 할 때,

(a+1)(b+1)(c+1)... (z+1) - 1

과 같다.

 

 

import sys

T = int(sys.stdin.readline())

for _ in range(T):
    n = int(sys.stdin.readline())
    
    wear = []
    for i in range(n):
        wear.append(sys.stdin.readline().split()[1])
    
    set_wear = tuple(set(wear))
    
    type = []
    for i in range(len(set_wear)):
        type.append(wear.count(set_wear[i]))

    result = 1
    for t in type:
        result *= (t + 1) 

    print(result - 1)

 

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다