[Python] BOJ no.9375 패션왕 신해빈

문제 링크

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

9375번: 패션왕 신해빈

---

문제 설명

이번 문제는 신해빈이라는 패션왕이 매번 다르게 입을 수 있는 옷의 조합 수를 구하는 문제이다.

headgear, eyewear, face와 같이 의상의 종류가 주어지고 의상의 종류가 주어지면 1개 이상의 의상이 주어진다.

 

의상의 종류를 고려할 때, 입지 않은 의상의 종류가 있어도 되지만 하나도 입지 않으면 안된다.

---

내 풀이

from itertools import combinations
t = int(input())

for _ in range(t):
  n = int(input())
  dic = dict()
  for __ in range(n):
    a, b = input().split()
    if b not in dic.keys():
      dic[b] = 0
    dic[b] += 1
  ans = 0
  for i in range(1, len(dic.keys())+1):
    for j in combinations(dic.keys(), i):
      if i == 1:
        ans += dic[j[0]]
      else:
        temp = 1
        for k in range(len(j)):
          temp *= dic[j[k]]
        ans += temp
  print(ans)

단순히 수학적으로 생각했으면 오히려 풀 수 있었는데, 전혀 생각이 나지 않았다. 고작 실버 3 문제에 이리도 흔들리다니... 아직 갈 길이 멀었구나...

 

처음 내 풀이의 프로세스는 다음과 같다.

1. 각 의상의 종류마다 의상의 개수를 저장한다.
2. 의상의 종류를 combinations 메서드를 활용해 조합을 구성한다.
3. 그 조합마다 생길 수 있는 조합 수를 더해가면서 최종 결과를 계산한다.

→ 당연히 시간초과로 안된다.. ㅎㅎ

^^;;

---

풀이 #1

t = int(input())

for _ in range(t):
  n = int(input())
  dic = dict()
  for __ in range(n):
    a, b = input().split()
    if b not in dic.keys():
      dic[b] = 0
    dic[b] += 1
  ans = 1
  for key in dic.keys():
    ans *= (dic[key] + 1)
  print(ans - 1)

문제 풀이는 아주 간단하다.

1. 기존 내 풀이처럼 각 의상의 종류마다 의상의 개수를 저장한다.
2. (의상의 개수 + 1)을 각 의상의 종류마다 계속해서 곱해나간다.
3. 마지막으로 1을 빼준다.

순서 2번, 3번이 조금 이해가 되지 않을 수 있는데 수학적으로 보면 오히려 간단하다.

 

총 조합의 개수 = (1번 의상의 개수 + 1) * (2번 의상의 개수 + 1) * (3번 의상의 개수 + 1) - 1

• 먼저 의상의 개수에 1을 더해주는 이유는 해당 의상이 사용되지 않는 경우를 의미한다.
• 그리고 마지막으로 1을 빼주는 이유는 1, 2, 3번의 의상 모두 사용되지 않는 경우를 배제하는 것이다!

---

Reference

https://hongcoding.tistory.com/60

[백준] 9375 패션왕 신해빈 (Python 파이썬)