[프로그래머스] 등굣길

1# 문제

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

 

2# 풀이

이 문제의 경우 DP를 이용한 풀면 쉽게 풀린다.

오른쪽과 아래쪽으로 밖에 갈 수 없기 때문에 임의의 위치(i,j)에서 경우의 수는 (i-1,j) + (i,j-1) 이다. 

public static int solution(int m, int n, int[][] puddles) {
	int answer = 0;
	int[][] matrix = new int[n + 1][m + 1];
	
    // puddles 표시
	for (int i = 0; i < puddles.length; i++) {
		matrix[puddles[i][1]][puddles[i][0]] = -1;
	}
       
    // 초기값 설정
	matrix[1][1] = 1;
	
    for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (i == 1 && j == 1)
				continue;
			if (matrix[i][j] == -1) {
				matrix[i][j] = 0;
			} else {
               	// 효율성 테스트시 int 값을 넘어갈 수 있기 때문에 항상 나눠줌
				matrix[i][j] = (matrix[i - 1][j] + matrix[i][j - 1]) % 1000000007;
			}
		}
	}
    
	answer = matrix[n][m];
    
	return answer;
}