[프로그래머스]등굣길 - DP

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

프로그래머스

 

기억해야할점들

 

첫번째, 문제확인

집에서 학교까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 return 하도록 solution 함수를 작성해주세요.

처음에 최단경로의 개수를 1000000007로 나눈 나머지를 리턴하라는 것을 못봐서 틀렸습니다.

또, 마지막에만 나눠주는 것이 아닌 계산할떄마다 해주어야 계산 중에 값이 오버해서 넘치지 않습니다.

 

두번째, 문제에서 보면 행과 열을 x,y 대칭으로

m, n에서 m이 열이고, n이 행인데 어처피 y=x 대칭이므로 결과는 같습니다.

 

세번쨰, puddles를 다 돌면서 확인하지 않고 map으로 만들어서 진행합니다.

 

 

코드입니다.

class Solution {
    int[][] DP;
    int[][] Puddles;
    public int solution(int m, int n, int[][] puddles) {
        int answer = 0;
        Puddles = new int[m][n];
        for(int i=0;i<puddles.length;i++){
            Puddles[puddles[i][0] - 1][puddles[i][1] - 1] = 1;
        }
        DP = new int[m][n];
        DP[0][0] = 1;
        for(int i=0; i<DP.length;i++){
            for(int j=0;j<DP[0].length;j++){
                if(Puddles[i][j] == 1) continue;
                if(i == 0 && j==0) continue;
                
                int leftside = (i-1 >= 0) ? DP[i-1][j] : 0;
                int upside = (j-1 >= 0) ? DP[i][j-1] : 0;
                
                DP[i][j] = (leftside + upside)%1000000007;
            }
        }
        // for(int i=0;i<DP.length;i++){
        //     for(int j=0;j<DP[i].length;j++){
        //         System.out.print(" "+DP[i][j]);
        //     }
        //     System.out.println();
        // }
        
        return DP[m-1][n-1];
    }
    
    
}