🔥[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 * $10^9$.

📃입출력 예

입출력 예 #1

Input : m = 3, n = 7
Output : 28

입출력 예 #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

🚨제한 사항

• 1 <= m, n <= 100

---

✏️풀이

문제에 제시된 예시를 기준으로 경우의 수를 구하다 보면서 한 가지 규칙을 발견할 수 있었다.
이전 경로들의 최단 경로 경우의 수의 합이 현재 경로의 최단 경로가 된다는 것이다.

이를 점화식으로 표현하면 다음과 같다.

grid[m][n] = grid[m-1][n] + grid[m][n-1]

이제 이 점화식을 코드로 옮겨 주기만 하면 된다.

그리드 초기화

그리드 전체를 우선 1로 채워준다.

for (int i = 0; i < m; i++) {
	for (int j = 0; j < n; j++) {
    	grid[i][j] = 1;
    }
}

점화식 적용

구해놓은 점화식을 그대로 적용시키기만 하면 문제를 간단히 해결할 수 있다.

for (int i = 1; i < m; i++) {
	for (int j = 1; j < n; j++) {
		grid[i][j] = grid[i-1][j] + grid[i][j-1];
	}
}

👾전체 코드

public static int uniquePaths(int m, int n) {
	int[][] grid = new int[m][n];

	// 그리드 초기화
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			grid[i][j] = 1;
		}
	}

	// 점화식 적용
	for (int i = 1; i < m; i++) {
		for (int j = 1; j < n; j++) {
			grid[i][j] = grid[i-1][j] + grid[i][j-1];
        }
    }
	return grid[m-1][n-1];
}

---

🔗문제 링크
💻Repository