LeetCode 코딩 문제 2021/06/18 - Unique Paths
[문제]
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
개 만큼나열한 것과 같다.
그런데 같은 것끼리는 순서에 상관없이 나열하면 되므로 조합을 사용하면 더 쉽게 구할 수 있다.
Author And Source
이 문제에 관하여(LeetCode 코딩 문제 2021/06/18 - Unique Paths), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@hemtory/LeetCode20210618
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
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
개 만큼나열한 것과 같다.
그런데 같은 것끼리는 순서에 상관없이 나열하면 되므로 조합을 사용하면 더 쉽게 구할 수 있다.
Author And Source
이 문제에 관하여(LeetCode 코딩 문제 2021/06/18 - Unique Paths), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@hemtory/LeetCode20210618저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)