★Combinatorics Intermediate I - 3 Solved★

★ 2407 조합 ★

import math
n,m=map(int,input().split())

print(math.factorial(n) // (math.factorial(n-m) * math.factorial(m)))

👻 위 공식만 정확히 알고 있으면 끝!  

---

★ 9375 패션왕 신해빈 ★

import sys
input=sys.stdin.readline

for _ in range(int(input())):
    n=int(input())
    fashion={}
    if n==0:
        print(0)
    else:
        for _ in range(n):
            clothes=input().split()
            if clothes[1] in fashion:
                fashion[clothes[1]]+=1
            else:
                fashion[clothes[1]] = 1
        l=list(fashion.values())

        answer=l[0]
        for i in range(1,len(l)):
            answer+=(answer*l[i])
            answer+=l[i]
        print(answer)

 

👻 알고리즘: hash table 구현 + combinatorics 2개

 

👻 ① 일단, 각 의상 종류별로 몇 개 있는지, 개수가 중요하므로 dictionary hash table을 구현하여 2가지 정보 {의상 종류: 해당 종류 내의 의상 개수}를 저장

→ hash table을 사용하므로각 종류별로 의상 개수를 update하는 연산은 O(1) 

 

👻 ② 적어도 한 개를 착용하는 모든 경우의 수는, 예를 들어 각 종류별 의상의 개수가 [3,2,1]일 경우 한 종류를 착용한 경우 3 + 2 + 1 / 두 종류를 착용한 경우 3*2 + 2*1 + 3*1 / 세 종류 모두를 착용한 경우 3*2*1이 된다.

→ itertools의 combinations를 활용해 모든 경우의 수를 나열하고, 각각의 내부 가짓수 곱들을 쭉 더하면메모리 초과 발생 (가짓수가 많아짐)

→ 따라서 조합론의 아이디어를 점화식을 세워 dp-table을 활용하거나, 입을 수 있는 모든 경우의 수를 계속 update한다.

 

※ N가지의 종류로 입을 수 있는 모든 경우의 수

→ a(i) (i=1...n) = i번째 종류의 의상 개수

→ Fashion(N) = N번째의 종류를 반드시 입는 모든 경우의 수

 

Fashion(N) = Fashion(N-1)*a(n) + a(n)

answer = Fashion(1) + Fashion(2) + Fashion(3) + .... + Fashion(N)

 

→ N번째 종류를 제외한, N-1번째 종류까지의 모든 경우의 수를 안다면, 각 경우의 수에서 마지막 a(n)을 곱해주면 된다.

→ 추가로, 앞의 모든 종류를 입지 않는다면, 마지막 종류는 반드시 입어야 하므로 a(n)을 더해주면 됨

 

→ 최종적으로 모든 Fashion() 결과를 더해주면 답 완성!

 

👻 hash-table로 필요 정보를 간략하게 저장하고, 점화식 idea로 조합론 모든 경우의 수를 구현하는 고난도 문제!

 

👻 조합론 요약 👻

Q. 각 옷의 종류별로 a,b.. ,x가지가 있다. 적어도 1개 이상의 옷을 입는 경우의 수는?

A. (a+1)*(b+1)* ... *(x+1) - 1

→ 각 종류별로 보았을 때 예를 들어 첫 번째 종류의 옷이 a가지가 있으면, 안입는 경우를 포함해 (a+1) 경우의 수 존재. 따라서 각각 1씩 더한 경우를 서로 모두 곱하고, 하나도 안 입었을 경우 단 1가지만 빼면 끝!

 

- 조합론 활용 -

import sys
input=sys.stdin.readline

for _ in range(int(input())):
    n=int(input())
    fashion={}
    if n==0:
        print(0)
    else:
        for _ in range(n):
            clothes=input().split()
            if clothes[1] in fashion:
                fashion[clothes[1]]+=1
            else:
                fashion[clothes[1]]=2
        l=list(fashion.values())

        answer=1
        for i in l:
            answer*=i
        print(answer-1)

---

★ 1010 다리 놓기 ★

 

import sys,math
input=sys.stdin.readline

for _ in range(int(input())):
    N,M=map(int,input().split())
    #MCN
    print(math.factorial(M)//(math.factorial(N)*math.factorial(M-N)))

 

👻 건널 수 있는 다리가 서로 겹치지 않는다는 건, 강 오른쪽 M개의 지점에서 N개의 지점이 도착할 N개의 도착점 개수를 고르기만 하기

 

👻 MCN 공식 활용

---