[JAVA] 프로그래머스 : 등굣길 (코딩테스트 고득점 kit > 동적계획법(Dynamic Programming))

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

코딩테스트 연습 - 등굣길

동적계획법 문제를 풀기위해서는 큰 문제를 작은 문제로 나누는 과정이 필요함

이 과정을 통해 점화식을 세우는게 중요함

그리고 메모제이션을 해서 시간을 줄이는게 중요함
=>값을 저장해놓음으로써 함수 호출의 시간을 단축시킬수 있으므로

메모제이션 방법으로는 아래와 같은 방법이 있음 
1. 반복문을 이용하여 미리 값들에 대한 계산을 다 해서 저장하는 방법 (BOTTOM-UP)
2. 그 순간 필요하면 계산해서 저장하는 방법(TOP-DOWN)

 

해결 방안

최단경로 구하는 방법

1. 최단 경로 구하는 방법을 이용하여 점화식을 구함(아래 코드 참고)

2. 점화식을 이용하여 최단 경로를 구하는 data를 메모제이션 해줌
이때 메모제이션 방법으로는 반복문을 이용하여 미리 값을 계산해주는 BOTTOM-UP 방식을 이용함

 

코드

// 등굣길
class Solution {
    public int solution(int m, int n, int[][] puddles) {
        int answer = 0;
        
        int[][] dp = new int[n+1][m+1];
        
        dp[1][1] = 1;
        // 최단경로 구하는 방법
        /*
          1 2 3 4
        1 1 1 1 1
        2 1 0 1 2 
        3 1 1 2 4
        */
        
        // 웅덩이는 -1이 됨
        for(int i=0; i<puddles.length; i++){
            dp[puddles[i][1]][puddles[i][0]] = -1;
        }
        
        for(int i=1; i<dp.length; i++){
            for(int j=1; j<dp[i].length; j++){
                // 웅덩이일 경우 0으로 바꿔줌
                if(dp[i][j] == -1){
                    dp[i][j] = 0;
                    continue;
                }
                
                // [1][1]~[1][m] 경우의 수 구해줌
                if(i==1 && j>1){
                    dp[i][j] = dp[i][j-1];
                    continue;
                }
                
                // [2][1] ~ [2][m] 경우의 수 구해줌
                if(i>1){
                    dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % 1000000007;
                }
            }
        }
        answer = dp[n][m];
        
        return answer;
    }
}