[BOJ][Python]9375번 풀이

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

9375번: 패션왕 신해빈

t = int(input())
for _ in range(t):
    n = int(input())
    cl = [input().split() for _ in range(n)]
    c = {i[1]:[] for i in cl}
    ans_l = []
    for i in cl:
        c[i[1]].append(i[0])
    for i in c.keys():
        ans_l.append(len(c[i]))
    ans = 1
    for i in ans_l:
        ans *= i+1
    print(ans-1)

저는 이런 방법이 있다는 건 처음 알았습니다. 어떻게 하면 백트래킹을 사용하지 않고 해당 문제를 계산할 수 있을지 도무지 생각이 떠오르질 않았는데요. 여러 n가지의 종류에서 한 종류만 중복하지 않고 고를 때, 두 가지만 중복하지 않고 고를 때...해서 n가지 까지 중복하지 않고 고르는 모든 경우의 수를 다 더해야하는 문제였는데 정말 간단하게 같은 값이 나오는 경우가 있었습니다. 그냥 모든 종류에서 1을 더한 수를 곱한 다음에 맨 마지막에 1을 빼주면 같은 값이 나오더라구요. 고등학생 시절에 경우의 수 문제를 그렇게 잘 푸는 편은 아니었지만 이런 스킬이 있는지는 또 몰랐네요.

 

예를 들어서 [1,2]와 [a,b,c]를 종류 중복 없이 고른다고 가정하면 하나만 고를 때의 경우에서 1,2,a,b,c 이렇게 5개가 나오고, 두 개를 고를 때는 (1,a),(1,b),(1,c),(2,a),(2,b),(2,c)이렇게 6개가 나오겠죠. 그래서 총 가짓수는 11개입니다. 그렇다면 위에서 말했던 1을 더한 수를 곱해서 다 더한 다음에 마지막에 1을 빼면 답이 같이 나오는지를 봐야겠죠. 3*4-1 = 11로 제대로 나오는 것을 볼 수 있습니다.

 

해당 방법이 가지는 풀이적 의미는 '해당 종류를 선택하지 않았을 경우' 를 임의로 추가해주는 방법이라고 합니다. 따라서 '뽑지 않는다를 선택하는 경우'가 생김으로써 하나를 뽑을 경우, 둘을 뽑을 경우를 일일이 구분할 필요가 없어지는 거죠. 마지막에 1을 빼주는 것은 알몸은 안된다고 했기 때문입니다. 즉 무조건 하나는 선택하는 경우가 마지노선이기 때문에 하나도 선택하지 않는 경우를 빼주는 겁니다.

 

도움이 되셨나요? 저는 이렇게 간단한 방법으로 풀어내는 스킬이 있을거라곤 생각도 못했네요. 역시 잘 모를 때는 시간을 투자해서 스스로 뚫는 것도 좋지만 이렇게 새로운 것을 찾아보면서 도움을 받는 것도 좋은 것 같습니다. 저는 꽤 외골수같은 면이 있어서 이 때 까지는 무슨 일이 있어도 혼자서 뚫는 것만이 가치 있다고 생각을 했었는데 요즘은 조금 융통성이 생긴듯한 기분입니다.