[프로그래머스][JAVA] 등굣길

programmers.co.kr/learn/courses/30/lessons/42898

코딩테스트 연습 - 등굣길

예제

대표적인 동적 계획법 문제였다

집을 기준으로 1 이라 두고 좌표의 왼쪽과 위의 값을 더하며 저장하는 방식으로 풀었다

 

class Solution {
    private static int[][] nodes;
    public int solution(int m, int n, int[][] puddles) {
        nodes = new int[n][m];

        for(int i=0;i<puddles.length;i++){
            nodes[puddles[i][1]-1][puddles[i][0]-1] = -1;
        }
        nodes[0][0] = 1;
        
        for(int i =0;i<n;i++){
            for(int j =0;j<m;j++){
                if(nodes[i][j]==-1){
                    nodes[i][j] = 0;
                    continue;
                }
                if(i!=0){
                    nodes[i][j]+=nodes[i-1][j]%1000000007;
                }
                if(j!=0){
                    nodes[i][j]+=nodes[i][j-1]%1000000007;
                }
                
            }
        }
        
        return nodes[n-1][m-1]%1000000007;
    }

    
}