✅ DP

문제

링크

1. 문제 접근 및 해결 로직

다리를 최대한으로 놓아야 하므로 서쪽 가장 위 사이트는 전부 연결이 되어야 하고, $n<=m$ 이므로 서쪽 가장 위 사이트는 동쪽 가장 위 사이트와 이어질 수도 있고 두번째..세번째 등등 과 이어질 수 있다.
각 경우에 따라 가능한 최대 연결 경우의 수를 구해보자.

$bridge[n][m]$ 을 서쪽에 사이트가 $n$개, 동쪽에 사이트가 $m$개 일때 다리를 놓을 수 있는 최대 경우의 수라고 하자.

즉,

• 1->1 연결될 경우 남은 다리를 연결되는 경우의 수는 $bridge[n-1][m-1]$
• 1->2 연결될 경우 남은 다리를 연결되는 경우의 수는 $bridge[n-1][m-2]$
  ...
• 1->i 연결될 경우 남은 다리를 연결되는 경우의 수는 $bridge[n-1][m-i]$
  (서쪽 사이트 개수 만큼 다리를 놓아야 하므로 $m-i$는 무한이 작아질 수 없고 $n-1$개까지만 작아질 수 있다.)

따라서 점화식은 아래와 같다.

• 정의
  $f(n,m)$ : 서쪽에 사이트가 $n$개, 동쪽에 사이트가 $m$개 일때 다리를 놓을 수 있는 최대 경우의 수
• 구하는 답
  $f(n,m)$
• 초기값
  $f(1,m)=m$
• 점화식
  $f(n,m)=sum(f(n-1,m-i)),(i=1,2,3...)(m-i>=n-1)$

2. 코드

3. 시간 복잡도 분석

경우의 수를 모두 구하므로
$O(N)$

4. 문제에서 중요한 부분

DP문제는 점화식을 도출하는 것이 중요하다.
Bottm Up(반복문)으로 풀지 Top Down(재귀)으로 풀지는 선택사항