99클럽 코테 스터디 40일차 TIL / [프로그래머스] 등굣길

오늘의 학습 키워드

---

DP

문제

---

https://school.programmers.co.kr/learn/courses/30/lessons/42898

• 플랫폼: 프로그래머스
• 문제명: 등굣길
• 난이도: Lv3

풀이

---

import java.util.*;

class Solution {
    
    public int solution(int m, int n, int[][] puddles) {
        int[][] grid = new int[n+1][m+1];
        
        for(int[] puddle : puddles) {
            grid[puddle[1]][puddle[0]] = -1;
        }
        
        grid[1][1] = 1;
        
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=m; j++) {
                if(i == 1 && j == 1) {
                    continue;
                }
                
                if(grid[i][j] == -1) {
                    grid[i][j] = 0;
                    continue;
                }
                
                grid[i][j] = grid[i-1][j] % 1_000_000_007 + grid[i][j-1] % 1_000_000_007;
            }
        }
        return grid[n][m] % 1_000_000_007;
    }
}

접근

• DP를 활용하여 풀이했습니다.
• grid 배열은 현재 좌표까지 최소 길이로 도달할 수 있는 경로의 개수를 의미합니다.
  • 즉 grid[n][m] ⇒ 집에서 학교까지 갈 수 있는 최단경로의 개수인 것입니다.
• 이동은 오른쪽과 아래로만 가능하기 때문에, 현재 위치로 올 수 있는 후보는 왼쪽에서 오는 경우, 위에서 오는 경우로 2가지입니다.
  • 이를 점화식으로 나타내면 다음과 같습니다

    grid[i][j] = grid[i-1][j] + grid[i][j-1];

• grid 배열을 순회하며, 바텀업으로 시작점부터 채워가며 최종 값을 도출해습니다.

소요 시간

30분