[알고리즘] 백준 9375 패션왕 신해빈 (파이썬 풀이)

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

9375번: 패션왕 신해빈

문제

해빈이는 패션에 매우 민감해서 한번 입었던 옷들의 조합을 절대 다시 입지 않는다. 예를 들어 오늘 해빈이가 안경, 코트, 상의, 신발을 입었다면, 다음날은 바지를 추가로 입거나 안경대신 렌즈를 착용하거나 해야한다. 해빈이가 가진 의상들이 주어졌을때 과연 해빈이는 알몸이 아닌 상태로 며칠동안 밖에 돌아다닐 수 있을까?

입력

첫째 줄에 테스트 케이스가 주어진다. 테스트 케이스는 최대 100이다.

• 각 테스트 케이스의 첫째 줄에는 해빈이가 가진 의상의 수 n(0 ≤ n ≤ 30)이 주어진다.
• 다음 n개에는 해빈이가 가진 의상의 이름과 의상의 종류가 공백으로 구분되어 주어진다. 같은 종류의 의상은 하나만 입을 수 있다.

모든 문자열은 1이상 20이하의 알파벳 소문자로 이루어져있으며 같은 이름을 가진 의상은 존재하지 않는다.

출력

각 테스트 케이스에 대해 해빈이가 알몸이 아닌 상태로 의상을 입을 수 있는 경우를 출력하시오.

 

해결코드

from collections import Counter

t = int(input())
for i in range(t):
    n = int(input())
    li = []
    for i in range(n):
        name, kind = input().split()
        li.append(kind)
    cnt = 1
    result = Counter(li)
    for i in result:
        cnt *= result[i] +1
    print(cnt-1)

문제풀이

예제입력에 있는 예시를 보면

hat headgear
sunglasses eyewear
turban headgear

위와 같은 경우일 때

경우의 수는 5가 나오고

mask face
sunglasses face
makeup face

위의 경우에는

경우의 수가 3이 나온다.

 

하나의 규칙이 있는데 (a의상종류의 의상 수+1)*(b의상종류의 의상 수+1)*.... -1 이 식으로 나온다.

의상 수에 1을 더해주는 이유는 그 의상종류를 입을수도 있고 안입을 수도 있기 때문이고

마지막에 1을 빼주는 이유는 모두다 안입을 경우는 빼주어야 하기 때문이다.

 

일단 코드를 보면

t에 테스트케이스를 입력받아주고

케이스 수만큼 for문을 돌려준다.

그리고 n에 의상수를 입력받아주고

의상 종류를 넣어줄 li라는 리스트를 하나 만들어준다.

그리고 n만큼 또 for문을 돌려주는데

의상이름인 name과 종류인 kind를 입력받아준다.

그리고 kind는 li에 추가시켜준다.(어차피 의상 종류만 식에 들어감)

그리고 for문을 탈출해서 cnt값은 초기에 1로 둔다.(0으로 두면 곱셈해도 0이기 때문이다)

result라는 변수에는 Counter함수를 써서 li에 있는 원소 값들의 원소별 개수를 센 것을 넣어준다.

이번에는 result값을 대상으로 for문을 돌리는데

앞에서 말했듯이 result[i]+1을 cnt에 계속해서 곱해주고

출력할때는 -1을 해서 출력하면 결과가 나오게 된다.