프로그래머스 - dp / 등굣길 / 자바 java

programmers.co.kr/learn/courses/30/lessons/42898?language=java

코딩테스트 연습 - 등굣길

이문제는 자주 보고 외워두는 것이 좋을 것 같다.

dp는 자주 푸는게 답인듯 하다..

그림으로 잘 설명되어있는 블로그 참고

velog.io/@ajufresh/%EB%93%B1%EA%B5%A3%EA%B8%B8

[프로그래머스] 등굣길 문제풀이 (Java)

풀이방법만 알면 간단하게 풀 수 있다

효율성 테스트를 위해서 100000007로 나눠주는 것을 잊지 말아야한다!

나중에 answer 계산할때도 꼭 나눠줘야 효율성 테스트를 통과할 수 있다.

class Solution {
    public int solution(int m, int n, int[][] puddles) {
        int answer = 0;
        int[][] route = new int[m][n];
        for(int i=0;i<puddles.length;i++){
            int x = puddles[i][0]-1;
            int y = puddles[i][1]-1;
            route[x][y]=-1;
        }
        
        route[0][0]=1;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(route[i][j]== -1){
                    route[i][j]=0;
                    continue;
                }
                if(i!=0){
                    route[i][j]+=route[i-1][j]%1000000007;
                }
                if(j!=0){
                    route[i][j]+=route[i][j-1]%1000000007;
                }
            }
        }
        answer = (route[m-1][n-1])%1000000007;
        return answer;
    }
}