[동적계획법] 커플 만들기 ( 조합 )

예제) 남자 m명과 여자 n명이 있다. 남자는 여자보다 많고 커플은 여자의 수만큼 생성된다. 여자는 키가 큰 순서로 선택할 수 있다. 남자는 키 순서대로 서있다. 한 여자가 한 남자를 선택했을 때, 다음 여자는 선택된 남자보다 키 큰 남자를 선택할 수 없다. 남성의 키가 모두 다를 때, 커플이 탄생할 수 있는 경우의 수를 구하라. 

 

 

( 개인적으로 이게 뭔 문제인지 감도 잘 안 잡혔다. 동적계획법에 억지로 문제를 끼어맞추다보니 이상한 문제가 탄생한거 같다. 그래도 한 번 풀어보자. )

 

 

결국 커플은 n개 탄생한다. 동적계획법을 발상하려면 두 가지를 고려하면 된다.

 

1) 큰 단위와 작은 단위에 공통으로 적용되는 원리를 발견한다. 

2) 큰 단위와 작은 단위를 분리한다.

 

 

 

첫 번째 여자는 3명의 남자를 선택할 수 있다. 

 

 

 

경우1, 경우2, 경우3

 

여자 4명이 남자 6명을 선택하는 경우는 다음과 같이 분리된다.

 

경우1 : 여자 3명이 남자 5명을 선택하는 경우

경우2 : 여자 3명이 남자 4명을 선택하는 경우

경우3 : 여자 3명이 남자 3명을 선택하는 경우

 

F(n,m)은 여자 n명이 남자 m명을 선택하는 경우의 수이다.

 

 

F(4,6) = F(3,6) + F(3,5) + F(3,4)

 

큰 단위인 4가 작은 단위인 3으로 분리되는 모습이다. 알고리즘을 코드로 짜서 구현하면 쉽게 답을 구할 수 있다.

 

---

 

동적계획법을 사용하지 않고 좀 더 쉽게 구할 수 있다. 

 

키 큰 여자의 선택은 키가 작은 여자들의 선택에 영향을 준다. 그래서 여자입장에서 보면, 키 큰 여자의 선택에 따라 경우가 분리되어 동적계획법 알고리즘이 적용해야 했다. 

 

그러나 남자 입장에서는 그냥 m명 중 n명 뽑으면 알아서 키순으로 연결된다. 여자가 5명 있고 남자가 8명 있으면 커플이 탄생할 경우의 수는 ₈C₅이다. 총 56가지이다. 

 

---

참고자료

2021년 7기 모집대비 SSAFY(삼성 청년 SW아카데미) SW적성진단 5일 완성