Today I Learned

오늘은 n모 회사의 코테를 봤다. 중간에 한 문제에 헤메서 시간을 엄청 낭비하고 결국 제대로 푼 문제가 없었다. 저번 h사보다 어렵게 느껴졌다. 뭔가 문제마다 실마리는 보이는데 완전한 solve가 어렵게 느껴졌다. 더 노력해야겠다.

등굣길

https://school.programmers.co.kr/learn/courses/30/lessons/42898

• 문제
  M X N 격자에서 왼쪽위(1,1)이 집, 오른쪽 아래(m,n)가 학교다.
  이차원배열 puddles가 웅덩이 좌표를 주면 웅덩이를 피해서 집에서 학교를 갈 수 있는 최단경로의 개수를 1000000007로 나눈 나머지를 구해라.

• 풀이 과정

1. 각 칸마다 시작점에서 그 칸까지 올 수 있는 경우의 수를 계속 누적해서 더하는 방식으로 풀었다.(DP 동적계획법 적용)

2. int[m][n] 배열을 하나 만든다.

3. 우선 웅덩이의 정보를 넣어야 하니 -1로 넣어준다.

4. 시작칸 값을 1로 넣고 이중 for문으로 값을 넣어준다.

5. -1이면(웅덩이면) 경우의 수가 없어야하므로 0을 넣어주고, x좌표가 0이 아니면 앞의 x좌표를 더하고 y좌표도 마찬가지로 한다.

6. 최종적으로 m-1, n-1의 값을 제출하면 끝.

• 생각해볼 부분
  효율성 테스트에서 계속 넘어가지 않아서 계속 헤멨다.
  원인은 중간과정에서 % 1000000007을 하지 않은것.
  나머지를 구하라는 문제는 항상 중간과정에서 값의 overflow가 발생할 수 있으므로 중간에 계속 나눠주는 것이 좋다.

• 구현 코드

import java.util.*;
class Solution {
    public int solution(int m, int n, int[][] puddles) {
        int answer = 0;
        
        int[][] map = new int[m][n];
        
        // 웅덩이
        for(int[] puddle : puddles){
            map[puddle[0]-1][puddle[1]-1] = -1;
        }
        
        map[0][0] = 1;
        
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(map[i][j] == -1) {
                    map[i][j] = 0;
                    continue;
                }
                if(i!=0){
                    map[i][j] += map[i-1][j] % 1000000007;
                }
                if(j!=0){
                    map[i][j] += map[i][j-1] % 1000000007;
                }
            }
        }
        answer = map[m-1][n-1];
        
        return answer % 1000000007;
    }
}