[프로그래머스] 동적계획법 - 등굣길

풀이방법

 

1. 중학교 때인가 배웠던 것처럼 숫자를 합하는 방식으로 진행한다.

	1	1	1
1	2	3	4
1	3	6	10

2. 갈 수 없는 곳은 -1, [m][0],[0][n] 에는 1로 초기화한다. (나머지는 자동 0 초기화)

	1	1	1
1	-1	0	0
1	0	0	0

3. 만약 [m][0],[0][n]에서 -1값이 있다면 그 다음 칸들은 절대 갈 수 없다 ((0,2)가 -1인 경우 (0,3)도 -1이 될 수밖에 없음)

	1	-1	-1
1	-1	0	0
1	0	0	0

4. 0인 칸들을 계산한다

map[i][j]=map[i-1][j]+map[i][j-1]

5. -1인 칸은 0으로 바꿔준뒤 다음 칸으로 넘어간다.

 

	static int solution(int m, int n, int[][] puddles) {
        
        int[][] map=new int[m][n];
        
        for(int i=1;i<m;i++) map[i][0]=1;
        for(int j=1;j<n;j++) map[0][j]=1;
        
        //물에 잠긴 곳은 -1
        for(int k=0;k<puddles.length;k++) {
        	int i=puddles[k][0]-1;
        	int j=puddles[k][1]-1;
        	map[i][j]=-1;
        	if(i==0) {
        		for(int x=j;x<n;x++) map[0][x]=0;
        	}
        	if(j==0) {
        		for(int x=i;x<m;x++) map[x][0]=0;
        	}
        }
        
        for(int i=1;i<m;i++) {
        	for(int j=1;j<n;j++) {
        		if(map[i][j]==-1) { 
        			map[i][j]=0;
        			continue;
        		}
        		map[i][j]=map([i-1][j]+map[i][j-1])%1000000007;
        	}
        }
        
        return map[m-1][n-1];
    }

 

정확도 문제는 모두 맞았지만 효율성 문제가 계속 오답이 나서

서칭해보니 계산 중간에 오버플로우가 난 것이 원인이라고 하여

 

map[i][j]=map[i-1][j]+map[i][j-1]%1000000007;

이렇게 수정해 주었더니 효율성 문제까지 모두 맞혔다