62. Unique Paths

문제)

다음과 같은 문제 상황이 주어졌습니다:

로봇이 m x n 크기의 격자(grid) 위에 있습니다.

로봇은 처음에 왼쪽 상단 모서리(grid[0][0])에 위치해 있으며, 오른쪽 하단 모서리(grid[m - 1][n - 1])로 이동하려고 합니다. 이때, 로봇은 오직 아래쪽이나 오른쪽으로만 이동할 수 있습니다.

두 정수 m과 n이 주어졌을 때, 로봇이 오른쪽 하단 모서리까지 도달하는 데 사용할 수 있는 고유한 경로의 수를 반환하세요.

테스트 케이스는 결과가 2 * 10^9 이하가 되도록 생성됩니다.

 

문제 난이도 : 중

 

소요시간 및 풀이)

dp를 이용해서 풀었다.

감이 잘 안잡히던 dp 알고리즘에 대해서 어느정도 이해가 가기 시작했다.

 

예를 들어 1,1의 목표 지점까지 가기 위해서는 반드시 0,1 또는 1,0을 거쳐야 한다.

모든 경로를 구해야 하니 0,1과 1,0을 거쳐가는 길을 찾으면 된다.

그 과정에서 첫 번째 행과 첫 번째 열은 경로가 1개이니 1로 값을 채워준다.

(아래 또는 오른쪽으로 밖에 못움직이기 때문.)

그 후, 경로를 순회하며 경로의 개수를 점차 더해나가면 정답을 구할 수 있다.

 

소요 시간 : 20분

 

정답 코드

class Solution 
{
public:
    int uniquePaths(int m, int n)
    {
        // m x n 크기의 DP 테이블 초기화, 모든 값을 0으로 초기화
        vector<vector<int>> paths(m, vector<int>(n, 0));

        // 첫 번째 행과 첫 번째 열은 경로가 1개
        for (int i = 0; i < m; i++)
        {
            paths[i][0] = 1; 
        }
        for (int j = 0; j < n; j++)
        {
            paths[0][j] = 1;
        }

        // DP테이블 채우기
        for (int i = 1; i < m; i++)
        {
            for (int j = 1; j < n; j++)
            {
                paths[i][j] = paths[i - 1][j] + paths[i][j - 1];
            }
        }

        // 오른쪽 하단 모서리에서의 경로 수 반환
        return paths[m - 1][n - 1];
    }
};