[실버 III] 9375번. 패션왕 신해빈

 문제 

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

9375번: 패션왕 신해빈

 사용 언어 

Python3

 풀이 과정 

실버 III인데 아래 채점 결과를 보면 알겠지만 생각보다 어렵게 풀었다..  끝까지 첫 번째 방법을 고수했으면 못 풀었을 것 같기도 하다...  스터디 전까지 못 풀어서 스터디원들의 풀이를 듣고 고쳐서 풀었다.

 

나는 아래처럼 조합을 모두 구해서 각 조합별로 가능한 가짓수를 곱하고 더하고를 반복했는데 당연히 시간이 오래걸렸다. 시간뿐만 아니라 메모리 초과라는 생소한 오류가 난 걸 보면 dict에 저장해야 하는 양이 너무 많았던 것 같다.

from itertools import combinations
from sys import stdin
input = stdin.readline

T = int(input())
for _ in range(T):
    answer = 0
    clothes = int(input())
    cloth_dict = {}
    for _ in range(clothes):
        cloth, type = input().split()
        if type in cloth_dict:
            cloth_dict[type] += 1
        else:
            cloth_dict[type] = 1
    # 옷 종류는 겹치지 않게
    combi = []
    cloth_keys = cloth_dict.keys()
    for x in range(len(cloth_keys)):
        combi.extend(combinations(cloth_keys, x+1))
    for types in combi:
        tmp = 1
        for type in types:
            tmp *= cloth_dict[type]
        answer += tmp
    print(answer)

 

중학교 때 풀었던 수학 문제를 생각해보면 간단하게 옷의 종류별로 입을지 안입을지, 그러니까 종류별 가능한 가짓수 + 1(안입는 경우)를 모두 곱한 다음 다 안입는(알몸이 되는) 경우 한 번을 빼면 됐다!

 

그렇게 여섯 번만에 맞았습니다!!

 

 제출 답안 

from sys import stdin
input = stdin.readline

T = int(input())
for _ in range(T):
    clothes = int(input())
    cloth_dict = {}
    for _ in range(clothes):
        cloth, type = input().split()
        if type in cloth_dict:
            cloth_dict[type] += 1
        else:
            cloth_dict[type] = 1
    # 해당 종류를 입을지 안입을지 모든 경우의 수 곱하기
    answer = 1
    for type in cloth_dict:
        answer *= cloth_dict[type] + 1
    # 알몸이 되는 경우 빼기
    print(answer - 1)

 

 다른 사람 풀이 

1. 숏코딩

import sys
ip=sys.stdin.readline
for _ in range(int(ip())):
    r=1
    l=[ip().split()[1]for _ in range(int(ip()))]
    for i in set(l):r*=(l.count(i)+1)
    print(r-1)

 

2. list 사용

import sys
input = sys.stdin.readline
T = int(input())
for _ in range(T):
    n = int(input())
    
    wear = []
    for i in range(n):
        wear.append(input().split()[1])
        
    set_wear = tuple(set(wear))
    
    gear = []
    for i in range(len(set_wear)):
        gear.append(wear.count(set_wear[i]))
        
    result = 1
    for t in gear:
        result *= (t + 1)
    
    print(result - 1)

➡ 옷 종류 개수만 확인해서 간단하게 답을 구하는 방식이다. 3년 전 채점 기준으로 56ms