[문제]

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

How many possible unique paths are there?

Example 1:

Input: m = 3, n = 7
Output: 28

Example 2:

Input: m = 3, n = 2
Output: 3
Explanation:
From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down

Example 3:

Input: m = 7, n = 3
Output: 28

Example 4:

Input: m = 3, n = 3
Output: 6

(요약) 로봇이 왼쪽 위에서 출발해서 오른쪽 아래까지 갈 수 있는 모든 방법을 구하라. (오른쪽과 아래로 한칸씩 움직일 수 있음)

[풀이]

var uniquePaths = function(m, n) {
  const grid = [];
   
  grid.push(new Array(n).fill(1));
   
  for(let i = 1; i < m; i++) {
    const tempArr = [1];
       
    for(let j = 1; j < n; j++) {    
      tempArr.push(grid[i - 1][j] + tempArr[j - 1]);
    }
       
    grid.push(tempArr);
  }
   
  return grid[m - 1][n - 1];
};

어릴 때 학교에서 배운 방법을 적용한 것이다.

특정 점으로 이동하는 경우의 수는 그 지점의 위까지 도달하는 경우의 수와 왼쪽까지 도달하는 경우의 수를 합한것이다.

그 방법을 적용한 것인데 그림으로 설명을 해야 이해가 쉽겠지만 일단 그런 방식으로 구현.

var uniquePaths = function(m, n) {
  return fac(m + n - 2) / (fac(m - 1) * fac(n - 1));
};

function fac(num) {
  let result = 1;
   
  for(let i = num; i >= 2; i--) {
    result *= i;
  }
   
  return result;
}

또 다른 방법으로 조합을 사용함.

아래쪽와 오른쪽을 각각 m - 1, n - 1개씩 총 m + n - 2개 만큼나열한 것과 같다.

그런데 같은 것끼리는 순서에 상관없이 나열하면 되므로 조합을 사용하면 더 쉽게 구할 수 있다.