clara-shin.js

/**
 * DP로 풀 수도 있고, 조합으로 풀 수도 있음
 *
 * 조합: (m+n-2)C(n-1)
 * n개의 원소 중에서 r개를 선택하는 경우의 수 (순서고려 안함)
 * nCr = n! / (r!(n-r)!)
 * 장점: 격자의 각 위치까지 경로의 수를 모두 알수 있어서 유연함, DP보다 시간복잡도 낮음
 * 단점: 큰 수의 팩토리얼을 계산해야 하므로 오버플로우가 발생할 수 있음
 *
 * 시간복잡도: O(min(m,n)) ➡️ min(m-1, n-1)까지 반복하는 루프 때문에
 * 공간복잡도: O(1) ➡️ 추가 배열 사용 안함, 단일변수만 사용
 */
/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function (m, n) {
  // 총 이동 횟수: 오른쪽 (n-1)번 + 아래쪽 (m-1)번 = m+n-2
  let N = m + n - 2;

  // 아래쪽으로 이동하는 횟수 또는 오른쪽으로 이동하는 횟수 중 더 작은 값 선택
  // 조합 공식에서 nCk = nCn-k 특성을 이용해 계산을 최적화
  let k = Math.min(m - 1, n - 1);

  // 결과 변수를 초기화
  let result = 1;

  // 조합 계산: nCk = (n * (n-1) * ... * (n-k+1)) / (k * (k-1) * ... * 1) 방식으로 계산
  for (let i = 1; i <= k; i++) {
    result *= N - (i - 1); // 분자 부분: n, n-1, n-2, ..., n-k+1
    result /= i; // 분모 부분: k, k-1, k-2, ..., 1
  }

  return result;
};