๐Ÿ”ฅ[99ํด๋Ÿฝ ์ฝ”ํ…Œ ์Šคํ„ฐ๋””] 40์ผ์ฐจ TIL - Unique Paths

HOONSSACยท2024๋…„ 8์›” 30์ผ
1

99Club Coding Test Study

๋ชฉ๋ก ๋ณด๊ธฐ
40/41
post-thumbnail

โณ๋ฌธ์ œ

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 * 10910^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

profile
ํ›ˆ์‹น์˜ ๊ฐœ๋ฐœ์—ฌํ–‰

2๊ฐœ์˜ ๋Œ“๊ธ€

comment-user-thumbnail
2024๋…„ 8์›” 30์ผ

์˜ˆ์ „์— ๋‹Œํ…๋„?์—์„œ ํ’€๋˜ ๋ฌธ์ œ ์ƒ๊ฐ๋‚œ๋‹น

1๊ฐœ์˜ ๋‹ต๊ธ€