프로그래머스 - 등굣길(Level 3)

class Solution {
    public int dp(int[][] memo,int i,int j){
        if (i < 1 || j < 1) { //경계 넘어가는거 체크
            return 0;
        }
        
        if(memo[i][j]!=-1){
            return memo[i][j];
        }
            
        memo[i][j]=(dp(memo,i,j-1)+dp(memo,i-1,j))%1000000007;
        return memo[i][j];
            
    }
    public int solution(int m, int n, int[][] puddles) {
        int[][] memo=new int[n+1][m+1];
        
        for(int y=0;y<memo.length;y++){
            for(int x=0;x<memo[y].length;x++){
                //경곗값은 1로
                if((y == 1 ) || (x == 1 ))
                    memo[y][x]=1;
                //나머진 -1로 
                else 
                    memo[y][x]=-1;
            }
        }
        for(int[] puddle:puddles){
            int x=puddle[0];
            int y=puddle[1];
            //웅덩이가 경계라인에 있을 경우 그 이후 라인은 다 0으로 해줘야 못지나감
            if(x==1){
                for(int index=y;index<memo.length;index++)
                    memo[index][1]=0;
            }
            if(y==1){
                for(int index=x;index<memo[y].length;index++)
                    memo[1][index]=0;
            }
            //웅덩이 부분은 0으로
            memo[y][x]=0;
        }
       
        
        
        int answer = dp(memo,n,m);
        return answer;
    }
}

 

 

1. 경계 넘어가는지 체크 할 생각 못함

2. 웅덩이가 경계라인에 있을 경우 생각 못함

나머지는 나의 힘으로 짰다.

 

 

---

다른날 풀었을 때 나의 코드

import java.util.*;

class Solution {
    public int dp(int y,int x,int[][] memo){
        if(memo[y][x]!=-1) 
            return memo[y][x];
        if(y<1||x<1) //범위 넘어가면 0 리턴
            return 0;
        
        memo[y][x]=(dp(y,x-1,memo) + dp(y-1,x,memo)) % 1000000007;
        return memo[y][x] ;
    }
    public int solution(int m, int n, int[][] puddles) {
        int[][] memo=new int[n+1][m+1];
        for(int i=0;i<memo.length;i++)
            Arrays.fill(memo[i],-1);
        
        memo[1][1]=1;
        for(int[] a:puddles){
            int y=a[1];
            int x=a[0];
            memo[y][x]=0; //웅덩이 0으로 초기화
        }
        
        return dp(n,m,memo);
        
    }
}