728x90
수학
-
[Python][백준] 9375번 패션왕 신해빈 문제 풀이Algorithm/백준 2022. 4. 14. 10:00
이 문제는 Python 딕셔너리(이하, dict) 자료구조와 조합론을 알면 쉽게 풀 수 있다. dict는 hashtable, hashmap 자료구조를 Python에서 구현한 것으로 {key: value}로 구성되어있다. dict를 이용하면 O(1) 시간복잡도로 데이터에 접근할 수 있어 매우매우 빠르다. 신해빈씨의 옷의 종류(c_type)를 key로 두고 옷의 이름(name)을 리스트로 만들어 value로 만들어 clothes를 정의하였다. 옷 입는 경우의 수를 구하자 옷의 종류에서 0개 혹은 1개를 선택해서 조합한 경우의 수를 구하고, 각 옷의 경우의 수를 모두 곱하면 된다. 아무것도 안 입는 경우 1을 빼고 출력하는 것을 잊지말자. # key0: [value0, value1...] # key1: [va..