백준 1010 - 다리 놓기

문제

알고리즘 분류)

• 수학
• 다이나믹 프로그래밍
• 조합론

문제를 이해해보면 중복없이 M개중 N개를 고르는 조합 (combination)을 구하는 것이다

mCn = m! / n! * (m-n)!

단순히 조합을 모두 찾는 것이 아닌 경우의 수만 구하면 되므로 함수로 팩토리얼을 구현해
수식을 계산해 주었다

소스코드

python)

def factorial(a):
    if a<=1:
        return 1
    else:
        return a*factorial(a-1)

T = int(input())

for i in range(T):
    N,M = map(int,(input()).split())
    print(factorial(M)//(factorial(N)*factorial(M-N)))

java script)

자바스크립트로는 factorial() 함수를 사용하니 머신입실론에 의해 오차가 있어 틀렸다는 채점이 나왔다.
BigInt를 사용해도 되어보이지만 그냥 점화식을 도출해 일반적인 DP로 해결하였다.

풀이)
N<=M<=30이므로 총 30*30의 2차원 배열을 만들어 주었다
N=M 으로 행과열이 같은 부분은 경우의 수가 1이므로 대각선은 모두 1이다
N은M보다 크지 않으므로 대각선 아래 부분은 고려하지않는다

행렬을 보면 빨간색 부분은 파란색 두개의 합으로 나타낼 수 있다
점화식 : dp[N][M] = dp[N-1][M-1] + dp[N][M-1]

let input = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");

const N = input.shift();
input = input.map((e) => e.split(" ").map((e) => parseInt(e)));

const arr = Array.from(new Array(30), () => new Array(30).fill(0));

arr[1][1] = 1;
for (let i = 0; i <= 29; i++) arr[0][i] = i + 1;
for (let i = 1; i <= 29; i++)
  for (let j = i; j <= 29; j++) arr[i][j] = arr[i - 1][j - 1] + arr[i][j - 1];

input.forEach((v) => console.log(arr[v[0] - 1][v[1] - 1]));