[백준] 9375 - 패션왕 신해빈 (python)

문제 링크

아무 생각 없이 한 달 전에 조합을 활용하여 노가다로 풀었다.

from itertools import combinations

t = int(input())
for i in range(t):
    l = []

    n = int(input())
    for j in range(n):
        val, category = map(str,input().split())
        l.append((val,category))
    c = []
    for j in range(1,len(l)):
        c = c + list(combinations(l,j))
    ans = []
    cnt = 0
    for j in c:
        d = {}
        for v, c in j:
            if c not in d:
                d[c] = 1
            else:
                d[c] += 1
        flag = False
        for num in d.values():
            if num >= 2:
                flag = True
                break
        if flag:
            continue
        cnt += 1
    print(cnt)

시간 초과도 아니고 메모리 초과가 떴다. 뭔가 조합을 활용하여 수학적인 생각을 보다 더 해야 할 거 같았고, 나는 그런 유형의 문제에 매우 쥐약이었기 때문에 다음을 기약했었다.

벼르고 벼르다 오늘 풀려고 했는데 당최 풀이법이 생각이 나지 않았다. 결국 40여 분 고민한 끝에 인터넷을 찾아보았다.

방식은 매우 간단했다.
1. 딕셔너리를 활용하여 옷의 종류별로 구분하고 그것의 개수를 센다.
2. 종류의 개수 + 그 종류에 대해 안 입는 경우(1)을 곱한다.
3. 알몸인 경우는 없기 때문에 1을 뺀다.

t = int(input())

for _ in range(t):
    d = {}
    c = int(input())
    for i in range(c):
        name, gen = map(str,input().split())
        if gen not in d.keys():
            d[gen] = 1
            continue
        d[gen] += 1
    ans = 1
    for i in d:
        ans *= ( d[i]+1) # 1을 더하는 이유는 안입는 경우
    print(ans-1) # 알몸인 경우 빼주기

허무할 정도로 쉬웠다. 분명 조합인 것과 딕셔너리를 활용해야한다는 것을 파악하는데 왜 로직을 제대로 못짜는지 모르겠다. 수포자라 그런가보다.

그럼에도 해내야지. 화이팅😥