[문제]
https://school.programmers.co.kr/learn/courses/30/lessons/42898
[풀이]
웅덩이가 있다면 그 길을 통해서 올 수 없으므로 계산을 하지 않는다.
위 경우를 제외하고는 좌표에서 벗어나지 않는 범위에서, 위에서 오는 경우의 수와 왼쪽에서 오는 경우의 수를 dp 배열에 더해줌으로써 계산 가능하다.
[코드]
class Solution {
public int solution(int m, int n, int[][] puddles) {
int answer = 0;
// 오른쪽과 아래쪽으로만 움직여 집에서 학교까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 return
//n, m. dp[i][j]
int[][] dp = new int[n+1][m+1];
int[][] map = new int[n+1][m+1];
for(int[] p:puddles){
int x = p[0];
int y = p[1];
map[y][x] = -1; //웅덩이
}
dp[1][1] = 1;
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
if(map[i][j]==-1){
continue;
}
if(i>1){
dp[i][j] += dp[i-1][j]%1000000007;
}
if(j>1){
dp[i][j] += dp[i][j-1]%1000000007;
}
}
}
answer = dp[n][m]%1000000007;
return answer;
}
}
'알고리즘 공부 및 문제 풀이 > 프로그래머스(PRO)' 카테고리의 다른 글
[pro] 프로그래머스 level3 72415 카드 짝 맞추기 (Java) - BFS, DFS (0) | 2023.01.17 |
---|---|
[pro] 프로그래머스 level3 43162 네트워크 (Java) - BFS (0) | 2023.01.17 |
[pro] 프로그래머스 level3 43105 정수 삼각형 (Java) - dp (0) | 2023.01.13 |
[pro] 프로그래머스 level3 43163 단어 변환 (Java) - DFS (0) | 2023.01.13 |
[pro] 프로그래머스 level3 49191 순위 (Java) - 플로이드 와샬 (0) | 2023.01.12 |