[LeetCode] 62. Unique Paths

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

Unique Paths - LeetCode

Unique Paths - Medium

 

 

로봇이 좌측상단에 있고, m*n 칸의 길이 있다. 도착지는 우측하단에 있을때, 로봇이 도착지로 가는 최단 경로의 수는 몇가지인지 구하는 문제다.

학교에서 경우의수를 구하면 단골로 나오는 문제기에 그 풀이 그대로 해주면 된다.

각 경로마다 해당 경로로 갈 수 있는 최단경로 가지수를 dp식으로 나타내주면 된다.

예를 들어 아래와 같이 있을때를 보자.

처음 맨 윗줄(i=0)과 맨 앞칸(j=0)은 출발지에서 바로가는 경로 뿐이므로 1이 된다.

1	1	1	1
1
1

이제 가장 처음 만나게 되는 (1,1)을 보자.

이곳에 최단으로 도달하기 위해서는 바로 윗칸에서 아래로 내려오거나, 바로 왼쪽칸에서 아래로 내려오는 경우가 있다.

그렇다면 (1,1)에 도달하는 경우의 수는 (0,1)에 도달하는 경우의 수 + (1,0)에 도달하는 경우의 수 가 된다.

나머지 (i,j)에 도달하는 경우의수 역시 (i-1,j) 에 도달하는 경우의 수 + (i,j-1)에 도달하는 경우의 수로 구해주자.

1	1	1	1
1	2	3	4
1	3	6	10

마지막으로 (m-1,n-1)을 리턴해주면 된다.

 

전체 풀이 코드

class Solution {
public:
    int uniquePaths(int m, int n) {
        int M[105][105];
        for (int i=0; i<m; i++) for (int j=0; j<n; j++) {
            if (i && j) M[i][j] = M[i-1][j] + M[i][j-1];
            else M[i][j] = 1;
        }
        return M[m-1][n-1];
    }
};