[boj1010] 2차원 DP와 combination 값들의 관계로 경우의 수 찾기

BOJ 1010 백준 1010 다리 놓기

Question

Solution

Combination 값을 찾는 문제로 볼 수 있다. 왼쪽에 3개 오른쪽에 5개의 사이트가 있다면 오른쪽 5개 중 3개를 고르는 문제이다. (=5C3)
따라서 팩토리얼을 활용해 combination 값을 구할 수 있다. 이때 미리 dict를 만들어둬서 사전에 계산한 팩토리얼 값들을 담아두면 좋다.

이번에는 dp로 접근해보았다.
2차원 배열을 만들어두고 세로는 왼쪽의 개수, 가로는 오른쪽의 개수로 생각한다. 그리고 5C3 = 4C3 * 5 / 2 라는 점화식을 생각해볼 수 있다.

PSEUDO

• 세로 N, 가로 M일 때의 값을 표시할 수 있는 dp list 생성, dp[i][j]는 왼쪽 i개 오른쪽 j개의 사이트가 있을 때의 경우의 수를 뜻함

• i==j 일때 dp[i][j] = 1

• i==1 일때 dp[i][j] = j

• def get_val(i,j):
  dp[i][j]가 있으면 바로 return

  ans = get_val(i,j-1) * (j / (i-j))
  dp[i][j] = ans
  return ans

코드는 아래 깃허브에
github