Python3
문제
https://www.acmicpc.net/problem/9375
키워드
- 수학
- 자료 구조
- 조합론
- 해시를 사용한 집합과 맵
문제 풀이
문제 요구사항
가진 의상들이 주어졌을 때 과연 알몸이 아닌 상태로 며칠동안 밖에 돌아다닐 수 있을까?
한번 입었던 옷들의 조합을 절대 다시 입지 않는다. 예를 들어 오늘 안경, 코트, 상의, 신발을 입었다면, 다음날은 바지를 추가로 입거나 안경 대신 렌즈를 착용하거나 해야 한다.
변수 및 함수 설명
- t : 테스트 케이스 (최대 100)
- n : 해빈이가 가진 의상의 수 n(0 ≤ n ≤ 30)
- name, category : 가진 의상의 이름과 의상의 종류 (같은 종류의 의상은 하나만 입을 수 있다.)
모든 문자열은 1이상 20이하의 알파벳 소문자로 이루어져있으며 같은 이름을 가진 의상은 존재하지 않는다. - clo : category: name 조합으로 담을 딕셔너리
- ans : 돌아다닐 수 있는 날의 수
풀이
- 옷 종류는 key, 이름은 value 값으로 구성한다.
- 만약 입력 받은 옷 종류가 clo 딕셔너리 안에 key값으로 존재하지 않는다면, 새로운 옷 종류이기 때문에 옷 종류를 1로 세팅한다.
- 만약에 이미 있는 것이라면 +1을 해준다.
- 이전에 입었던 옷들의 조합으로 입지 않으려면 모든 종류의 옷을 (개수 + 1)하고, 이를 누적곱해주면 된다.
- 알몸인 상태는 제외해야 하므로 -1을 해준다.
최종 코드
t = int(input())
for _ in range(t):
clo = {}
n = int(input())
for _ in range(n):
name, category = list(input().split())
if category not in clo.keys():
clo[category] = 1
else:
clo[category] += 1
ans = 1
for i in clo:
ans *= clo[i] + 1
print(ans-1)피드백
딕셔너리 value에 계속 string 값을 그대로 넣으려고 했다. 하나의 key에 다중 value를 넣으려고 하니까 더 복잡해지고 어려워졌다. 생각의 전환..이라고 할 수 있을지 모르겠지만 필요했다!
I mean