BOJ 9375번 : 패션왕 신해빈

예제를 보면 알겠지만, 문자열이 꽤나 길어서.... 편하게 python을 사용하였다.

솔직히 말해서 두번 틀렸다...ㅎㅎ...

옷의 조합이 꼭 2개의 조합일 것이라고만 생각해서 경우의 수를 짜다보니 3개 이상의 조합을 빼먹을 것이다.

 

일단, 문자열 입력에서 띄어쓰기를 기준으로 뒤에 있는 옷의 종류만 알면 되기에 split()을 통해 뒷 단어만 따로 때서 dict 형에 집어 넣었다. Dict형을 사용한 이유는 옷의 종류가 같은지 다른지를 판단할때 A in ex_dic를 사용하면 매우 편해서 ㅎㅎㅎ

이후 딕셔너리의 밸류값만 따로 리스트로 만들어 연산을 수월케 했다.

 

이제 알고리즘을 알아보자.

옷의 종류 a,b,c가 각각 2,3,4개 있다고 가정하고, 각 원소의 갯수에 따른 조합의 경우의 수를 따져보자.

 

1개의 조합일때:

     2+3+4 

2개의 조합일때:

     (2*3) + (2*4) + (3*4)

3개의 조합일때:

     2*3*4

위의 모든 값을 더하면, 중복되지 않는 모든 조합의 경우의 수를 알 수 있다.

이때, 각 옷 종류의 갯수를 미지수로 바꾸어 생각해보고, 모두 더해보면 아래와 같다.

 

a+b+c+(ab)+(bc)+(ca)+abc

 

어.... 중학교의 냄새가 살짝쿵 나는데....

 

abc + (ab)+(bc)+(ca) + a + b + c = (a+1)(b+1)(c+1)-1

 

위처럼 표현 할 수 있다!!!!

옷의 종류가 4개이든, 5개이든 모두 저 꼴과 같으므로 수식을 작성 할 수 있다!

 

<소스코드>

for x in range(int(input())):
    dic = {}
    res = 1
    for i in range(int(input())):
        _str = input().split()
        if(_str[1] in dic): dic[_str[1]] += 1
        else:  dic[_str[1]] = 1
    _list = list(i+1 for i in dic.values())
    for i in _list:
        res*=i
    print(res-1)
    

 

<문제>

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

9375번: 패션왕 신해빈