[파이썬] 백준 9375번 패션왕 신해빈

문제 확인

9375번: 패션왕 신해빈

 

• 시간 제한 : 1초
• 메모리 제한 : 128MB

 

나의 풀이

못 풀었다. 시도한 풀이는 다음과 같다.

시간 복잡도만 생각하지 말고 메모리도 생각하면서 문제를 풀어야 겠다는 교훈을 얻었다...

• 여러 타입의 옷이 입력됐을 때 타입의 종류를 조합으로 결정한 뒤  풀이를 시도했다.
• 타입의 종류가 클 경우 조합 선택 시 메모리 초과가 발생했다.
  • 시간 복잡도 말고 메모리에 대해서 고민해보자. 
• 메모리 초과를 해결하기 위해 생성된 조합을 generator로 처리했을 땐 시간 초과가 발생했다.

from itertools import combinations
import sys

T = int(input())
for _ in range(T):
    n = int(input())
    # type별 분리
    cloth_type = {}
    # 최종 합
    combi_num = 0
    for _ in range(n):
        name, t = sys.stdin.readline().rstrip().split()
        if t not in cloth_type:
            cloth_type[t] = []
        # type에 해당하는 제품 입력
        cloth_type[t].append(name)
    type_num = len(cloth_type)
    type_list = list(cloth_type.keys())
    # type 조합 개수를 바꿔가며 계산
    for i in range(1, type_num + 1):
        if i == 1:
            combi_num += n
        else:
            # i개 만큼 type 뽑기
            # list로 담으니 메모리 초과가 발생해 generator로 사용
            combi_type = (combinations(type_list, i))
            # type 조합 선택
            for com in combi_type:
                # 조합 내 type 선택
                temp_num = 1
                for combi_name in com:
                    temp_num *= len(cloth_type[combi_name])
                combi_num += temp_num
    print(combi_num)

다른 사람 풀이

(종류별 옷의 수) + 1을 전부 곱해주고 (해당 종류의 옷을 안 입는 경우의 수를 포함한 것)

알몸의 경우의 수인 1만 빼주면 된다.

T = int(input())

for _ in range(T):
    n = int(input())
    
    #0일때 탈출
    if n == 0:
        print(0)
        continue
    
    wearable = dict()
    for _ in range(n):
        wear_name, wear_type = map(str, input().split())
        
        #같은 옷 분류 중, 이름은 버리고 종류만 가져가기
        if wear_type in wearable.keys():
            wearable[wear_type] += 1
        else:
            wearable[wear_type] = 1
        
        #(각 옷의 수)+1 한 것을 곱해줌
        answer = 1
        for key in wearable.keys():
            answer *= wearable[key] + 1
    #안입는 경우만 뺴줌
    print(answer - 1)

#212 백준 파이썬 [9375] 패션왕 신혜빈