[파이썬] 백준 9375 : 패션왕 신해빈

[파이썬] 백준 9375 : 패션왕 신해빈

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

9375번: 패션왕 신해빈

실버 3

수학, 자료 구조, 조합론, 해시를 사용한 집합과 맵

---

접근

두 개 이상의 사건이 동시에 일어나면 각각의 경우의 수를 곱해야 하며, 이를 곱의 법칙이라 한다.

3종류의 티셔츠와 2종류의 바지를 하나씩 골라 입을 수 있는 경우의 수는

티셔츠를 고를 수 있는 경우의 수 3과 바지를 고를 수 있는 경우의 수 2의 곱인 6이라고 할 수 있다.

 

문제 조건에서 같은 종류의 옷은 반드시 하나만 입을 수 있다는 점에서 유의하여 접근했다.

 

코드 풀이

from collections import defaultdict
import sys
from itertools import combinations
T = int(sys.stdin.readline())
for t in range(T):
    clothes = {}
    cnt = 1
    N = int(sys.stdin.readline())
    for n in range(N):
        clothe, kind = sys.stdin.readline().rstrip().split()
        if clothes.get(kind) == None:
            clothes[kind] = set()
        clothes[kind].add(clothe)
        
    for k in clothes.keys():
        cnt *= len(clothes.get(k)) + 1
    print(cnt - 1)

 

 

첫번째 케이스 :

hat headgear
sunglasses eyewear
turban headgear

 

를 입력 했을 때

5가 출력된다.

 

hat과 turban은 같은 종류의 옷이므로 하나씩만 선택할 수 있다.

이를 딕셔너리로 정리하면 {'headgear' : (hat, turban), 'eyewear' : sunglasses}가 될 것이다.

 

headgear를 고르는 경우의 수는 hat 또는 turban을 고르는 경우의 수와 headgear에서 아무 것도 고르지 않는 경우의 수 를 합한 3이된다.

문제조건에 따라 headgear에서 아무것도 고르지 않고 eyewear의 sunglasses만 골라 입을 수도 있기 때문이다.(선글라스만 착용하는 경우)

 

 

마찬가지로 eyewear의 경우의 수 또한 sunglasses를 착용하는 경우와 착용하지 않는 경우를 합해 2라고 할 수 있다.

 

각각의 경우의 수를 곱하면 3x2 = 6이다.

문제 조건중에 알몸이 아닌 상태로 의상을 입을 수 있는 경우의 수를 출력하라고 되어있기 때문에

모든 경우의 수에서 아무 것도 입지 않은 경우의 수를 제외시켜야 한다.

따라서 해당 케이스의 경우의 수는 (3x2)-1 = 5가 된다.

 

옷의 종류가 복수로 존재하는 경우, 각각의 종류에서 옷을 입을지 말지는 선택할 수 있는 부분이므로 한가지 옷을 입는 경우와 입지 않는 경우를 포함하여 곱을 했으나, 그 경우의 수에는 모든 종류에서 옷을 선택하지 않는 경우의 수가 포함되어 있기 때문에 1을 빼주어야 한다.

 

 

두 번째 케이스:

mask face
sunglasses face
makeup face

를 입력하면 3이 출력된다.

 

모두 face류의 옷이기 때문에 해당 경우의 수는 당연히 3이 된다. 같은 종류의 옷을 복수로 선택할 수 없기 때문이다.

첫번째 케이스와 마찬가지로 옷을 선택할 수 있는 경우의 수 3과 선택하지 않는 경우의 수 1을 더하면 4가 된다.

그러나 입력 받은 옷의 종류가 한가지이기 때문에 아무 것도 선택하지 않는 경우의 수 하나를 빼주어야 한다.

따라서 해당 케이스의 경우의 수는 3이 된다.

 

 

두 케이스를 통해 이를 공식으로 정리하면

(A종류의 옷의 개수 +1) x (B종류의 옷의 개수 +1) x (C종류의 옷의 개수 +1) ... - 1

임을 알 수 있다.

 

from collections import defaultdict
import sys
from itertools import combinations
T = int(sys.stdin.readline())
for t in range(T):
    clothes = {}
    cnt = 1
    N = int(sys.stdin.readline())
    for n in range(N):
        clothe, kind = sys.stdin.readline().rstrip().split()
        if clothes.get(kind) == None:
            clothes[kind] = set()
        clothes[kind].add(clothe)
        
    for k in clothes.keys():
        cnt *= len(clothes.get(k)) + 1
    print(cnt - 1)

 

값을 입력받을 때, 옷의 종류를 key로, 옷의 이름을 value로 설정한 딕셔너리를 먼저 만들었는데 value가 다수로 존재하는 경우를 구현하기가 힘들었다. 딕셔너리는 리스트처럼 append함수가 먹히지 않기 때문이었다.

 

그래서 딕셔너리에 key값이 입력되있지 않은 경우에 set를 넣고, add함수를 사용해 value값을 추가시키는 방법을 적용했다.

clothes[kind].add(clothe)는 해당 키가 이전에 입력되었던지 여부에 상관없이 항상 수행되어야 하므로 else문으로 구분짓지 않도록 했다.

 

get함수는

딕셔너리 이름.get(key이름)

형식으로 해당 key값이 가지는 value를 반환한다.

그 길이에 + 1를 한것들을 곱한 값에 최종적으로 - 1을 계산함으로써 위의 공식을 구현할 수 있다.