[프로그래머스] 등굣길

프로그래머스 level3 등굣길

 

소요시간 : 1시간 19분

 

세상 오래걸렸다

처음에 잘못 생각해서 3차원 배열로 했다가 갈아엎었다 ㅋㅋㅋ

 

자신 칸 기준 위와 왼쪽의 값을 더해서 마지막 목적지 값을 반환하면 된다.

 

그런데 isPuddles 함수를 지우고 처음부터 map 에다가 puddles 를 표시하는 게 좋을 것 같다.

class Solution {
	int[][] Puddles;
    public int solution(int m, int n, int[][] puddles) {
    	Puddles = puddles;
    	int[][] map = new int[n+1][m+1];
    	map[1][1] = 1;
    	for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				if((i == 1 && j == 1) || isPuddle(i, j)) continue;
				
				if(i-1 <= n) {
					map[i][j] += map[i-1][j] % 1000000007;
				}
				if(j-1 <= m) {
					map[i][j] += map[i][j-1] % 1000000007;
				}
				map[i][j] %= 1000000007;
			}
		}
    	
    	return map[n][m] % 1000000007;
    }
    public boolean isPuddle(int x, int y) {
    	for (int i = 0; i < Puddles.length; i++) {
			if(Puddles[i][0] == y && Puddles[i][1] == x) return true;
		}
    	return false;
    }
}