Life Engineering
[프로그래머스] 등굣길 (Java) 본문
https://programmers.co.kr/learn/courses/30/lessons/42898
class Solution {
public int solution(int m, int n, int[][] puddles) {
int[][] dp=new int[n+1][m+1];
boolean[][] isPuddles=new boolean[n+1][m+1];
for (int i=0; i<puddles.length; i++){
int x=puddles[i][0];
int y=puddles[i][1];
isPuddles[y][x]=true;
}
dp[1][1]=1;
for (int i=1; i<=n; i++){
for (int j=1; j<=m; j++){
if (i==1 && j==1) continue;
if (isPuddles[i][j]) continue;
dp[i][j]=(dp[i][j-1]%1000000007)+(dp[i-1][j]%1000000007);
}
}
return dp[n][m]%1000000007;
}
}
문제의 조건을 보면, 위에서 오기, 왼쪽에서 오기만 가능하다. 즉 출발점에서 (i,j)까지 오는 가능한 경로의 수는 그 전 (i-1,j), (i, j-1) 까지의 경로의 수을 더한 값이다. dp[i][j]=dp[i][j-1]+dp[i-1][j] 라는 점화식을 얻을 수 있다.
출발지, 웅덩이인 경우 값을 더하지 않는다.
나는 IsPuddles라는 배열을 만들어서 웅덩이 여부를 표시해줬는데, dp 배열에 웅덩이의 위치를 -1로 표시해서, 만약 -1 값을 만났을 때 0으로 바꾸는 식으로 진행해도 된다.
'Problem Solving' 카테고리의 다른 글
[프로그래머스] n진수 게임 (Java) (0) | 2022.03.15 |
---|---|
[BOJ 17142] 연구소3 (Java) (0) | 2022.03.15 |
[BOJ 17136] 색종이 붙이기 (Java) (0) | 2022.03.10 |
[프로그래머스] n^2 배열 자르기 (Java) (0) | 2022.03.09 |
[프로그래머스] 배달 (Java) (0) | 2022.03.09 |