[Python] 백준 9375번 - 패션왕 신해빈

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

9375번: 패션왕 신해빈

 

처음에는 전체적인 로직을 생각하지 않고 그냥 테스트케이스만 보고 풀었더니 틀렸다.

하나씩 비교해가면서 노가다하는 방법으로 풀었는데

한 번 틀리고 다시 생각해보니 왠지 조합 같아서 알고리즘 분류를 확인했다. -> 조합론 맞았음

 

그리고 나서 조합으로 어떻게 풀 지 생각해보는데 잘 떠오르지 않고 헷갈려서 구글링을 했다.

 

찾아보니 옷의 종류별로 분류를 하여 각각의 종류에 대해 (해당 종류의 옷 개수 + 해당 종류를 안 입는 경우(1))를 곱해주는 방식의 문제였다.

그렇게 곱해준 후에 아무것도 안 입는 알몸인 경우 1가지를 빼주면 된다.

 

로직 찾는 데에 주력했으면 좀 더 빨리 쉽게 풀 수 있었을 것 같은데.. 아직 갈 길이 멀다. 🙃

 

 

#정답코드

import sys
input = sys.stdin.readline

t = int(input()) #test case 개수
for i in range(t):
    n = int(input()) #의상 수
    clothes = {}
    for j in range(n):
        c_n, c_t = input().split() #clothes_name, clothes_type

        #종류별로 분류
        if c_t not in clothes.keys():
            clothes[c_t] = 1
        else:
            clothes[c_t] += 1
    
    ans = 1
    for i in clothes: #i: key
        ans *= (clothes[i]+1) #해당 종류는 안 입는 경우 포함
    print(ans-1) #알몸인 경우 제외

 

 

 

#틀린 코드 (노가다)

어차피 틀린 코드지만 대충 이런 식으로 노가다 했다는 걸 기록하기 위해 첨부함.

import sys
input = sys.stdin.readline

t = int(input()) #test case 개수
for i in range(t):
    n = int(input()) #의상 수
    clothes = []
    for j in range(n):
        c_n, c_t = input().split() #clothes_name, clothes_type
        clothes.append((c_n, c_t))
    ans = n
    types = []
    typescheck = []
    for j in range(n):
        types.append(clothes[j][1])
        typescheck.append({clothes[j][1]})
        for k in range(n):
            if clothes[k][1] not in types:
                types.append(clothes[k][1])
                if set(types) not in typescheck:
                    typescheck.append(set(types))
                    ans += 1
                else:
                    del types[-1]
        types = []
    print(ans)

 

출력초과 원인: 디버깅할 때 확인용으로 사용한 print함수 정리 안 해서..