📌 구해야 하는 정답

서쪽에는 N개의 사이트(다리를 놓을 수 있는 곳)이 있고, 동쪽에는 M개의 사이트(다리를 놓을 수 있는 곳)이 있습니다.

이 때 서쪽과 동쪽 사이트를 연결해 다리를 놓을 수 있는 경우의 수를 구하는 문제입니다

조건

• N ≤ M이라고 합니다
• 다리는 서로 겹치면 안된다고 합니다.

📌 풀이 하기

1️⃣ 연결할 수 있는 다리의 경우의 수를 어떻게 구할 수 있을까?

사실 이 문제는 두 가지 방법으로 풀이할 수 있습니다.

1. 조합
2. DP

저희는 DP를 공부하고 있으니까 DP로 먼저 풀이해보겠습니다.

작은 문제 조건부터 하나씩 살펴보겠습니다.

N = 1 일 때

1. N = 1, M = 1

   

2. N= 1, M = 2

   

3. N = 1, M = 3

   

규칙이 보이시나요?