[백준] 9375 패션왕 신해빈 (python 파이썬)

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

9375번: 패션왕 신해빈

---

아이디어

1. 조합

• 처음에 문제를 봤을 때 방법을 몰라서 조합 라이브러리를 사용함.
• 테스트 케이스와 n의 최대가 적어 가능할 거라 생각했지만 다시 생각해보니 조합이면 경우의 수가 엄청 많아지니 
• 시간 초과가 떴다.

2. 수학

• 어릴 때 배웠던 경우의 수 문제를 생각하면 금방 풀 수 있다.
• 딕셔너리와 같이 쓰면 매우 간편하게 해결 가능.

---

코드 설명

    cloth = {}
    result = 1
    n = int(input())
    for _ in range(n):
        name, type = sys.stdin.readline().rstrip().split()

        if not type in cloth:
            cloth[type] = 1
        else:
            cloth[type] += 1

    for i in cloth:
        result *= (cloth[i] + 1)

    print(result - 1)

코드를 짜는데 어려운 부분은 없고 수학으로 접근하면 매우 간단하다.

 

문제에서 해빈이는 적어도 1개만 걸치면 밖에 나갈 수 있다. 즉 옷을 입는 모든 경우의 수에서 전부다 안 입는 경우를 제외해서 계산하면 된다.

 

예를 들어 상의 2개, 바지 3개가 있다면 (2 + 1(상의를 안 입는 경우)) * (3 + 1(바지를 안 입는 경우)) - 1

으로 총 경우의 수는 11이다.

 

딕셔너리에 key를 옷의 종류로 정한다.

옷이 이미 있는 종류면 key에 해당하는 값에 +1 해주고 아니라면 새롭게 key를 추가해주면 된다.

 

최종 값에 위에서 말했듯이 -1(모든 옷을 안 입는 경우)을 해주면 끝이다.

---

전체 코드

import sys

T = int(input())

for _ in range(T):
    cloth = {}
    result = 1
    n = int(input())
    for _ in range(n):
        name, type = sys.stdin.readline().rstrip().split()

        if not type in cloth:
            cloth[type] = 1
        else:
            cloth[type] += 1

    for i in cloth:
        result *= (cloth[i] + 1)

    print(result - 1)