[Baekjoon 9375 / Python / 실버3] 패션왕 신해빈

문제

 

수학, 조합론, 해시 테이블 문제이다.

문제 자체는 단순하고 금방 해결할 수 있을 것 같지만 나에겐 의외로 힘들었다. 수학을 잘 하는 사람이라면 금방 풀 것 같다.

 

# 수학, 조합론, 해시 테이블

import sys

input = sys.stdin.readline

# 테스트 케이스 개수만큼 반복

N = int(input())

for _ in range(N):

    n = int(input()) # 의상 개수

    clothes = {}

    # 의상 입력받기, 의상 이름은 필요가 없음

    for _ in range(n):

        _, category = input().split()

        clothes[category] = clothes.get(category, 0) + 1 # 의상 종류 증가시키기

   

    # 경우의 수 계산

    total = 1

    for _, value in clothes.items():

        total *= value + 1

   

    # 아무 옷도 입지 않은 경우를 제외하고 출력

    print(total - 1)

 

우선, 실버3이다보니 모든 가능한 조합을 브루트포스해도 괜찮겠지 싶어서 생각을 해봤는데, 의상이 30종류라면 2의30승, 약 10억번 연산이 필요해서 이건 아니다 싶었다. 심지어 이 10억번 연산을 최대 100번 할 수도 있다.

 

그래서 분명 효율적인 방법이 있을 것이라 생각했고, 그것은 조합론 알고리즘을 이용하는 것이었다. 알고리즘이자 여러 분야에서 사용되는 조합의 경우의 수를 구하는 공식이 있었다.

 

총 경우의 수 = ((카테고리1 개수 + 1) * (카테고리2 개수 + 1) * (카테고리3 개수 + 1) .... * (카테고리n 개수 + 1)) - 1

이 공식을 이용하면 길이 1부터 n까지의 중복 없는 모든 경우의 수를 구할 수 있으며 O(N)에 해결할 수 있다. 이건 이해하려기 보다는 그냥 외우는 게 맞는 것 같다.

 

각 개수에 1을 더하는 이유는 해당 옷을 입지 않는 경우도 경우의 수에 포함하기 때문이다.

마지막에 1을 빼는 이유는 모든 옷을 입지 않는 경우를 제외하기 때문이다.

 

입력받는 옷의 "이름"은 어차피 중복되지 않기 때문에 필요가 없어서 _, category 로 입력받았다.

clothes.get(category, 0)의 뜻은 clothes 딕셔너리에서 key가 category인 요소의 value를 가져오는 것이며, 만약 해당 카테고리가 존재하지 않는다면 즉시 key로써 추가하고 value를 0으로 만든다는 뜻이다.

마지막 경우의 수를 계산할 때, 딕셔너리는 순회할 수 없기 때문에 clothes.items()로 튜플화해서 순회했다.

 

 

결과