[DP] 64. Minimum Path Sum - Java

문제 바로가기

Minimum Path Sum - LeetCode

 

오늘의 추천 문제입니다. 맨위에 하나씩 뜨는게 추천 문제가 맞나?? 암튼 매일 바뀌는 거기에 뜬 문제입니다.

m x n 크기의 2차원 배열이 주어지고 왼쪽 맨 위(grid[0][0])에서 오른쪽 맨 아래(grid[m-1][n-1])까지의 경로의 합 중 가장 작은 값을 구하는 문제입니다.

 

제약 조건을 보면

• 1 <= m, n <= 200
• 0 <= grid[i][j] <= 100

 

요래 되어 있어서 그냥 dfs + 백트래킹으로 접근했습니다. 근데 시간 초과가 뜨네용.ㅋ

 

그래서 아~ 얘는 DP 구나~ 하고 포기하려던 찰나.. 조금만 생각해보니 점화식이랄 것도 없이 너무 간단히 풀릴 것 같아 코드를 후루룩 써내려갔습니다. 그러고는 스근하게 맞춰서 자신감이 생겨 정리해봅니다.

 

접근 1. 백트래킹

class Solution {
  public int[][] dir = {{0, 1}, {1, 0}};
  public int answer = Integer.MAX_VALUE;
  public int m, n;

  public int minPathSum(int[][] grid) {
    m = grid.length;
    n = grid[0].length;

    dfs(grid, 0, 0, 0);

    return answer;
  }

  public void dfs(int[][] grid, int sum, int y, int x) {
    if (!isIn(y, x)) return;
    if (sum + grid[y][x] >= answer) return;

    sum += grid[y][x];

    if (y == m - 1 && x == n - 1) {
      answer = sum;
    }

    for (int i = 0; i < 2; i++) {
      dfs(grid, sum, y + dir[i][0], x + dir[i][1]);
    }
  }

  public boolean isIn(int y, int x) {
    if (0 <= y && y < m && 0 <= x && x < n) return true;
    return false;
  }
}

 

먼저 생각한 백트래킹 코드입니다. DFS를 타주는데요, 현재의 Minimum Path Sum 보다 내가 가려는 곳의 합이 더 크면 얘는 더이상 볼 필요가 없어서 적절한 가지치기를 해줄 수 있습니다.

 

근데 그래도 안됩니다. 얘는 걍 다른 방법으로 풀어야 합니다.

 

접근 2. DP

class Solution {
  public int[][] dir = {{0, 1}, {1, 0}};
  public int m, n;

  public int minPathSum(int[][] grid) {
    m = grid.length;
    n = grid[0].length;

    for (int y = 0; y < m; y++) {
      for (int x = 0; x < n; x++) {
        if (y == 0 && x == 0) continue;
        int left = isIn(y, x - 1) ? grid[y][x - 1] : Integer.MAX_VALUE;
        int top = isIn(y - 1, x) ? grid[y - 1][x] : Integer.MAX_VALUE;

        grid[y][x] += Math.min(left, top);
      }
    }

    return grid[m - 1][n - 1];
  }

  public boolean isIn(int y, int x) {
    if (0 <= y && y < m && 0 <= x && x < n) return true;
    return false;
  }
}

저는 DP를 참 못합니다. 그래서 이 문제도 걍 안풀랬습니다.

근데 가만 생각해보면.. 앞에 봐줘야 하는 부분이 나의 왼쪽 && 윗쪽 밖에 없습니다. 얘네들 중 더 작은 친구와 내가 현재 있는 위치의 합을 구하면 걔가 바로 그 위치에서의 Minimum Path Sum가 되는 것이죵. 그렇게 O(m * n) 타임으로 grid 배열을 착실히 채워주면 마지막 오른쪽 맨 아래 grid[m-1][n-1]의 값이 정답이 됩니다.^^

 

 

감사합니다!!!!