99클럽 코테 스터디 40일차 TIL < Unique Paths >

오늘의 문제

 

 

	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.

	 

	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
	 

	Constraints:

	1 <= m, n <= 100

 

학습 키워드

 

---

 

동적계획법

---

 

문제 풀이

1. 

 

---

코드

 

class Solution {
    public int uniquePaths(int m, int n) {
        Combinatorics combinatorics = new Combinatorics(m+n-2);
        return (int)combinatorics.C(m+n-2,n-1);
    }
}
class Combinatorics{
    private static final long MOD = 2147483647L;
    long[] fac;

    public Combinatorics(int n){
        this.fac = new long[n+1];
        fac[0] = 1L;
        for(int i=1;i<=n;i++) fac[i] = fac[i-1]*i%MOD;
    }

    private long powMod(long x, long n){
        if(n == 0) return 1L;
        long t = powMod(x,n/2);
        if(n%2 == 0) return t*t%MOD;
        return t*t%MOD*x%MOD;
    }

    public long C(int n,int r){
        if(r==0) return 1L;
        return (fac[n]*powMod(fac[n-r]*fac[r]%MOD,MOD-2))%MOD;
    }
}

 

 
 
오늘의 회고