[programmers] 등굣길

문제 풀이 : 2021.05.12

풀이

처음 풀 때 모든 재귀호출을 이용한 동적계획법으로 풀었는데 정확성 테스트는 통과했지만 효율성 테스트는 통과하지 못했음
반복문을 이용한 동적계획법 사용

1	1	1	1
1	0	1	2
1	1	2	4

(j,i) 위치까지 도달할 수 있는 가지수 = (j-1,i) + (j,i-1)
점화식 : dp[j][i] = dp[j-1][i]+dp[j][i]
해당 문제는 주어진 좌표가 (가로,세로) 이므로 주의해야함

코드

public class Solution {
 public int solution(int m, int n, int[][] puddles) {
   int[][] dp = new int[n][m];

   for (int[] puddle : puddles)
     dp[puddle[1] - 1][puddle[0] - 1] = -1;

   dp[0][0] = 1;

   for (int i = 0; i < n; i++) { 
     for (int j = 0; j < m; j++) {

       if(dp[i][j] == -1) { 
         dp[i][j] = 0;
         continue;
       }
       if(i != 0)
         dp[i][j] += dp[i - 1][j] % 1000000007; 
       if(j != 0)
         dp[i][j] += dp[i][j - 1] % 1000000007; 
     }
   }

   return dp[n - 1][m - 1] % 1000000007;
 }

문제 출처 링크