[Programmers] 등굣길 Java

 

동적 계획법(Dynamic Programming) > 등굣길

 

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

프로그래머스

 

 

처음 코드(효율성 0점)

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

 

효율성 실패

 

질문하기 탭을 보니 1_000_000_007로 나눈 나머지를 구하지 않아서 실패했다는 글을 보고 마지막 문장만         return route[m][n] % 1_000_000_007;

이렇게 수정했다.

 

하지만 효율성 테스트 똑같이 실패

 

        		if(route[i-1][j] == -1) route[i][j] += route[i][j-1];
        		else if(route[i][j-1] == -1) route[i][j] += route[i-1][j];
        		else route[i][j] += (route[i-1][j] + route[i][j-1]) % 1_000_000_007;
        	}
        }
        return route[m][n];

 

계산 과정에서 나누어봤지만 효율성 테스트 5에서 시간 초과가 떴다.

 

        		if(route[i-1][j] == -1) route[i][j] += route[i][j-1] % 1_000_000_007;
        		else if(route[i][j-1] == -1) route[i][j] += route[i-1][j] % 1_000_000_007;
        		else route[i][j] += (route[i-1][j] + route[i][j-1]) % 1_000_000_007;
        	}
        }
        return route[m][n];

모든 계산 결과에서 나머지를 구해서 통과했다.

 

 

 

제출 코드

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