백준 9375 패션왕 신해빈

패션왕 신해빈

문제는 백준에서 확인 할 수 있다.

✔ 접근방법

• 조합

옷의 종류를 key로 하는 딕셔너리(해시테이블)을 만든 후,
가능한 조합의 개수를 구함

✔ 코드

from itertools import combinations

def solution(dic):
    answer = 1
    key_arr = list(dic.keys())
    
    for key in key_arr:
        answer *= (dic[key] + 1)
    
    answer -= 1
    
    print(answer)
    
'''
## 메모리 초과
def solution(dic):
    answer = 0
    possible_comb = []
    keys = list(dic.keys())

    for key in keys:
        possible_comb.append([key])

    if len(keys) >= 2:
        for i in range(2,len(keys)+1):
            possible_comb.extend(list(combinations(keys,i)))

    # print(possible_comb)
    
    for target in possible_comb:
        num = 1
        for i in range(len(target)):
            num *= len(dic[target[i]])
        else:
            answer += num

    print(answer)
'''

if __name__ == "__main__":
    TC = int(input())
    
    for _ in range(TC):
        dic = {}
        n = int(input())
        for _ in range(n):
            name, kind = input().split()
            if dic.get(kind, None) == None:
                dic[kind] = 1
            else:
                dic[kind] += 1

        solution(dic)
    

☝ 팁

이전에 똑같은 문제를 프로그래머스에서 풀었었는데, 그럼에도 불구하고 또 틀렸던 문제

각 카테고리별로 입지않는 경우를 포함해서 경우의 수를 구하고, 어떠한 것도 입지 않는 경우의 수인 1을 빼주면 쉽게 계산이 가능함

메모리초과가 난 이유는, 어떤 옷들로 조합이 가능한지를 일일히 찾으려고 했기 때문.
문제에서 요구하는 답은 가능한 경우의 수 였기에 모든 케이스를 알 필요는 없음.