[백준] 9375번
패션왕 신해빈
PYTHON
복잡한 듯 보이지만 해답 자체는 단순한 조합 문제이다.
하지만 코드를 작성할 때 조금 까다로운 요소가 포함된다.
고등수학 확률과 통계에서 볼 수 있는 수학 문제이다.
A가 N개, B가 K개 C가 P개 존재한다고 할 때, 반드시 전부 입을 필요는 없지만
A,B,C에서 최소한 한 개는 고르는 조합의 개수를 구하는 문제이다.
예를 들어, 모자가 a, b 바지가 c, d, e가 있다고 하자.
모자에서는 a를 쓰는 경우, b를 쓰는 경우 또는 쓰지 않는 경우의 세 가지가 존재한다.
바지에서는 c를 입는 경우, d를 입는 경우, e를 입는 경우 또는 입지 않는 네 가지가 존재한다.
따라서 모자와 바지를 조합하는 방법은 3*4의 12가지에서 아무것도 선택하지 않는 한 가지 경우를 제외하는 11가지이다.
소스 코드로 살펴보자.
reduce를 사용하는 방법
파이썬에는 리스트의 원소들을 전부 곱하기 위해 functools 라이브러리 안에 reduce 함수가 있다.
간단히 사용법을 살펴보면 다음과 같다.
reduce의 계산 과정은
((1x2)x3) 의 형태이다. 처음 두 원소를 곱해서 리스트에 들어가고 이 값이 다시 x로 뒤에 3이 y로 들어와서 계산되는 형태이다.
우리의 문제는 리스트 원소에 1을 더해서 곱해야 한다.
그런데 단순히 lambda x,y (x+1)*(y+1) 로 계산하면 앞서 계산한 결과에 또 1을 더해서 뒤의 원소와 곱하게 된다.
따라서 계산된 결과에 1을 뺀 값이 리스트에 들어가도록 해야지 다음 계산에 1을 더해도 문제가 없다.
소스 코드는 아래와 같다.
counter를 이용한 방법
Counter 함수는 리스트 내의 원소의 개수를 세서 dictionary의 형태로 반환한다.
예를 들어, [1, 2, 3, 1, 1]에 Counter를 씌우면 {1:3, 2:1, 3:1}이 반환된다.
문제에서 동일한 종류의 옷이 동일한 이름을 가지는 경우는 없다고 했기 때문에 입력에서 a 값은 필요없다.
어떤 종류의 옷이 몇 개 존재하는 지만 알면된다.
따라서 입력마다 b 값(옷의 종류) 을 리스트에 삽입하고 그 결과에 Counter를 씌운다.
그럼 어떤 종류의 옷이 몇 개 존재하는 지 딕셔너리 형태로 반환되고 이 값을 s에 저장한다.
이제 딕셔너리에서 value 값만 1씩 더해서 곱해주고 그 결과에서 아무것도 고르지 않은 경우만 하나 빼준다.
