링크

문제 링크

문제 설명

계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다.

아래 그림은 m = 4, n = 3 인 경우입니다.

가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n)으로 나타냅니다.

격자의 크기 m, n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매개변수로 주어집니다. 오른쪽과 아래쪽으로만 움직여 집에서 학교까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 격자의 크기 m, n은 1 이상 100 이하인 자연수입니다.
  • m과 n이 모두 1인 경우는 입력으로 주어지지 않습니다.
• 물에 잠긴 지역은 0개 이상 10개 이하입니다.
• 집과 학교가 물에 잠긴 경우는 입력으로 주어지지 않습니다.

입출력 예

풀이

1. 코드 가독성 차원에서 주어진 m과 n에서 한 칸씩 배열을 더 할당한다.
2. 이차원 map 배열의 값을 모두 1로 초기화하되, (n,1) 또는 (1,n)인 곳에 물 웅덩이가 있다면 거기서부터 아래로 또는 오른쪽으로 전부 0으로 만든다.
3. 그래서 점화식을 작성할 땐, 물웅덩이인 곳 map[i][j] == 0인곳이면 continue하고 아니면 윗칸과 왼쪽칸의 합을 더한다!
4. 최종적으로 map[n][m]을 리턴해주면 끝.

정말 기본적인 dp문제인데 자꾸 시간초과가 아닌 런타임에러가 나는것이다.

진짜 뭐지 싶어서 질문하기에 바로 달려갔다.

그래서 문제에서 주어지는 웅덩이인 puddles이 행과 열이 반대로 뒤바뀌어 주어진다는 것을 알았다...

문제 출제자가 더 원망스러웠던건 그렇게 행과 열을 바꿀거면 왜 테스트케이스엔 (2,2)의 경우를 줬냐는 것이다.

뭐 근데 그렇게 많은 시간을 낭비하진 않았으니 그냥 넘어간다!

아 그리고 이 문제에서 나머지 연산 (A + B) % mod = (A % mod + B % mod) % mod 법칙을 알고가자!

코오롱 인성검사 및 코딩테스트 합격메일이 날아왔고 2/8일날 면접이 잡혔다. 면접이 오랜만이라서 좀 긴장되긴하지만 그래도 합격하자!

코드

class Solution {
    static int[][] map;
    public int solution(int m, int n, int[][] puddles) {
        int answer = 0;
        map = new int[n + 1][m + 1];
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++)
                map[i][j] = 1;
        for(int[] puddle : puddles) {
            if(puddle[0] == 1)
                for(int i = puddle[1]; i <= n; map[i++][1] = 0);
            else if(puddle[1] == 1)
                for(int i = puddle[0]; i <= m; map[1][i++] = 0);
            else map[puddle[1]][puddle[0]] = 0;
        }
        for(int i = 2; i <= n; i++){
            for(int j = 2; j <= m; j++) {
                if(map[i][j] == 0) continue;
                map[i][j] = (map[i - 1][j]%1000000007 + map[i][j - 1]%1000000007) %1000000007;
            }
        }
        return map[n][m];
    }
}