티스토리 뷰
Problem
Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.
Example 1:
Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.
Example 2:
Input: grid = [[1,2,3],[4,5,6]]
Output: 12
Constraints:
- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 200
- 0 <= grid[i][j] <= 200
Solution
이 문제는 2D 그리드 내에서 왼쪽 위 모서리에서 오른쪽 아래 모서리로 이동하면서 숫자가 적힌 칸을 지날 때, 지나가는 경로의 숫자 합을 최소화하는 문제입니다.
동적 계획법(Dynamic Programming)을 사용하여 문제를 해결할 수 있습니다.
package io.lcalmsky.leetcode.minimum_path_sum;
public class Solution {
public int minPathSum(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
for (int i = 1; i < m; i++) {
grid[i][0] += grid[i - 1][0];
}
for (int j = 1; j < n; j++) {
grid[0][j] += grid[0][j - 1];
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);
}
}
return grid[m - 1][n - 1];
}
}
- 첫 번째 for 루프: 이 루프는 그리드의 첫 번째 열을 따라 내려가면서 각 칸까지의 최소 경로 합을 계산합니다. 즉, 위에서 아래로 내려오면서 각 칸에 이전 칸까지의 합을 더해줍니다. 이렇게 하면 첫 번째 열의 각 칸에는 해당 칸까지의 최소 경로 합이 계산됩니다.
- 두 번째 for 루프: 이 루프는 그리드의 첫 번째 행을 따라 오른쪽으로 이동하면서 각 칸까지의 최소 경로 합을 계산합니다. 위와 마찬가지로, 왼쪽에서 오른쪽으로 이동하면서 각 칸에 이전 칸까지의 합을 더해줍니다. 이렇게 하면 첫 번째 행의 각 칸에는 해당 칸까지의 최소 경로 합이 계산됩니다.
- 세 번째 for 루프: 이 두 개의 중첩된 루프는 그리드의 나머지 부분을 탐색하면서, 각 칸까지의 최소 경로 합을 계산합니다. 각 칸까지의 최소 경로 합은 현재 칸의 값에 왼쪽 칸까지의 최소 경로 합 또는 위쪽 칸까지의 최소 경로 합 중 더 작은 값을 더하여 계산됩니다.
- 마지막으로, 우측 하단 모서리의 값인 grid[m - 1][n - 1]을 반환하면서 왼쪽 위 모서리에서 오른쪽 아래 모서리로 이동하는 최소 경로 합을 구하게 됩니다.
Test
package io.lcalmsky.leetcode.minimum_path_sum;
import org.junit.jupiter.api.DisplayName;
import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.assertAll;
import static org.junit.jupiter.api.Assertions.assertEquals;
class SolutionTest {
@Test
@DisplayName("주어진 grid 에서 왼쪽위부터 오른쪽 아래로 이동하는 경로 중 최소 합 구하기")
public void givenGrid_whenFindMinimumPath_thenCorrect() {
assertAll(
() -> test(new int[][]{
{1, 3, 1},
{1, 5, 1},
{4, 2, 1}
}, 7)
);
}
private void test(int[][] given, int expected) {
// when
Solution minimumPathSum = new Solution();
int actual = minimumPathSum.minPathSum(given);
// then
assertEquals(expected, actual);
}
}
'Algorithm > LeetCode' 카테고리의 다른 글
[LeetCode] 48. Rotate Image (0) | 2023.08.23 |
---|---|
[LeetCode] 114. Flatten Binary Tree to Linked List (0) | 2023.08.22 |
[LeetCode] 2095. Delete the Middle Node of a Linked List (0) | 2023.08.02 |
[LeetCode] 735. Asteroid Collision (0) | 2023.08.01 |
[LeetCode] 2390. Removing Stars From a String (0) | 2023.07.31 |
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- proto3
- 스프링 데이터 jpa
- 스프링 부트 튜토리얼
- Spring Boot JPA
- leetcode
- JSON
- Spring Boot
- 클린 아키텍처
- 스프링부트
- Linux
- gRPC
- Jackson
- QueryDSL
- intellij
- JPA
- spring boot application
- 스프링 부트
- 헥사고날 아키텍처
- r
- 함께 자라기 후기
- @ManyToOne
- Spring Boot Tutorial
- 함께 자라기
- Spring Data JPA
- 스프링 부트 회원 가입
- spring boot app
- 스프링 부트 애플리케이션
- spring boot jwt
- 알고리즘
- Java
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
글 보관함