[파이썬 Python/알고리즘] LeetCode - Unique Paths

//GitHub https://github.com/vellimole0621

vellimole0621 - Overview

 

62. Unique Paths

 

문제 - https://leetcode.com/problems/unique-paths/

Unique Paths - LeetCode

문제 설명

 

There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The test cases are generated so that the answer will be less than or equal to 2 * 109.

=> m * n 위의 로봇이 가장 왼쪽 위에 위치하여 있을 때, 가장 오른쪽 아래로 가는 경우의 수를 구하라. 단, 로봇은 아래 또는 오른쪽으로

이동할 수 있다.

 

내 풀이 :

로봇이 위치한 장소 제외, 가야하는 수는 각각 아래쪽 m -1, 오른쪽 n-1 이다. > 행 또는 열이 1 인 경우, 경우의 수는 1이고. 그렇지 않은 경우, 조합을 이용해 계산한다. 

 

# 62. Unique Paths
# https://leetcode.com/problems/unique-paths/


class Solution:
    def uniquePaths(self, m: int, n: int) -> int:

        if m is 1:
            return 1
        elif n is 1:
            return 1
        else:
            real_num = m + n - 2

            if m - 1 <= n - 1:
                wat_num = m - 1
            else:
                wat_num = n - 1

            real_num_re = real_num
            wat_num_re = wat_num

            for i in range(1, wat_num):
                real_num_re = real_num_re * (real_num - i)

            for j in range(1, wat_num):
                wat_num_re = wat_num_re * (wat_num - j)

            return int(real_num_re / wat_num_re)