728x90
https://leetcode.com/problems/unique-paths/description/
[문제]
m x n 그리드에 로봇이 있습니다. 로봇은 처음에 왼쪽 상단 모서리(즉, grid [0][0])에 있습니다. 로봇은 오른쪽 하단 모서리
(즉, grid[m - 1][n - 1])로 이동하려고 합니다. 로봇은 어느 시점에서든 아래 또는 오른쪽으로만 이동할 수 있습니다. 두 정수 m과 n이 주어지면 로봇이 오른쪽 하단 모서리에 도달하기 위해 취할 수 있는 가능한 고유한 경로의 수를 반환합니다. 테스트 케이스는 답이 2 * 109보다 작거나 같도록 생성됩니다.
[입출력 예]
[풀이]
오른쪽과 아래로만 이동할 수 있는 점을 고려하여 로봇이 갈 수 있는 모든 경로를 구하면 됩니다.
먼저 위치에 대해서 나타낼 2차원 배열을 선언합니다.
val dp = Array(m) { IntArray(n) }
그리고 첫 번째 행과 첫 번째 열에 대해선 경로가 1개밖에 없습니다. (각 모서리에 붙어 이동하는 경우)
for (i in 0 until m) {
dp[i][0] = 1
}
for (j in 0 until n) {
dp[0][j] = 1
}
로봇이 위치 (i, j)에 도달하는 경로의 수는 (i-1, j)에서 오는 경로의 수(dp [i-1][j])와 (i, j-1)에서 오는 경로의 수(dp [i][j-1])를 더한 값입니다. 점화식으로 정리하자면, dp [i][j] = dp [i-1][j] + dp [i][j-1]입니다.
for (i in 1 until m) {
for (j in 1 until n) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
}
}
return dp[m - 1][n - 1]
dp [m-1][n-1]에는 로봇이 오른쪽 하단 모서리로 도달할 수 있는 고유한 경로의 수가 저장되므로 연산 이후 반환해 주면 됩니다.
아래는 전체 코틀린 코드입니다.
fun uniquePaths(m: Int, n: Int): Int {
val dp = Array(m) { IntArray(n) }
for (i in 0 until m) {
dp[i][0] = 1
}
for (j in 0 until n) {
dp[0][j] = 1
}
for (i in 1 until m) {
for (j in 1 until n) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
}
}
return dp[m - 1][n - 1]
}
(+ 점화식 유도 내용 추가 예정)
728x90
