[코딩테스트] 등굣길

문제

---

등굣길 문제 바로가기

제출 코드(JAVA)

---

코드 제출

class Solution {
    public int solution(int m, int n, int[][] puddles) {
        int[][] road = new int[m+1][n+1];


        // road 초기화
        road[1][1] = 1;

        for (int[] puddle : puddles) {
            road[puddle[0]][puddle[1]] = -1;
        }


        // 계산
        for (int i = 1; i < road.length; i++) {
            for (int j = 1; j < road[i].length; j++) {
                if (i == 1 && j == 1) {
                    continue;
                } else if (road[i][j] == -1) {
                    road[i][j] = 0;
                    continue;
                } else {
                    road[i][j] = (road[i][j-1] + road[i-1][j]) %  1_000_000_007;
                }
            }
        }

        return road[m][n] ;
    }

}

경로 총 갯수를 구하기 위해 테두리부터 덧셈을 더하는 것까지는 쉽게 가능.
1. (0,1), (1,0) 이 웅덩이임에도 불구하고 0의 가짓수가 나오지 않는걸 캐치하는게 핵심
즉, 테두리를 1로 채우고 덧셈을 하지 않는다
2. 효율성 검증을 위해 각 계산마다 1_000_000_007를 나누는게 핵심 2.
총 수를 계산하기엔 범위를 벗어난다.

정확성 테스트

정확성  테스트
테스트 1 〉	통과 (0.02ms, 51.9MB)
테스트 2 〉	통과 (0.02ms, 52.1MB)
테스트 3 〉	통과 (0.03ms, 52MB)
테스트 4 〉	통과 (0.03ms, 52.4MB)
테스트 5 〉	통과 (0.05ms, 52.6MB)
테스트 6 〉	통과 (0.04ms, 52.6MB)
테스트 7 〉	통과 (0.04ms, 53.8MB)
테스트 8 〉	통과 (0.05ms, 51.4MB)
테스트 9 〉	통과 (0.04ms, 53MB)
테스트 10 〉	통과 (0.02ms, 52.1MB)
효율성  테스트
테스트 1 〉	통과 (0.73ms, 52.3MB)
테스트 2 〉	통과 (0.31ms, 52.9MB)
테스트 3 〉	통과 (0.37ms, 52.9MB)
테스트 4 〉	통과 (0.53ms, 51.8MB)
테스트 5 〉	통과 (0.45ms, 52.4MB)
테스트 6 〉	통과 (0.60ms, 51.6MB)
테스트 7 〉	통과 (0.34ms, 54.1MB)
테스트 8 〉	통과 (0.60ms, 52.4MB)
테스트 9 〉	통과 (0.60ms, 52.2MB)
테스트 10 〉	통과 (0.59ms, 52.9MB)

제출 코드(Python)

---

코드 제출

def solution(m, n, puddles):
    road = [[0 for j in range(n+1)] for i in range(m+1)]

    road[1][1] = 1

    for x, y in puddles:
        road[x][y] = -1

    for i in range(1, m+1):
        for j in range(1, n+1):
            if road[i][j] == -1:
                road[i][j] = 0
                continue
            elif i != 1:
                road[i][j] = (road[i-1][j] + road[i][j-1]) % 1000000007
            elif j != 1:
                road[i][j] = road[i-1][j] + road[i][j-1] % 1000000007

    return road[m][n]

정확성 테스트

정확성  테스트
테스트 1 〉	통과 (0.01ms, 10.2MB)
테스트 2 〉	통과 (0.02ms, 10.3MB)
테스트 3 〉	통과 (0.03ms, 10.2MB)
테스트 4 〉	통과 (0.06ms, 10.3MB)
테스트 5 〉	통과 (0.08ms, 10.4MB)
테스트 6 〉	통과 (0.06ms, 10.2MB)
테스트 7 〉	통과 (0.06ms, 10.2MB)
테스트 8 〉	통과 (0.13ms, 10.3MB)
테스트 9 〉	통과 (0.06ms, 10.4MB)
테스트 10 〉	통과 (0.02ms, 10.4MB)
효율성  테스트
테스트 1 〉	통과 (2.95ms, 10.4MB)
테스트 2 〉	통과 (1.20ms, 10.4MB)
테스트 3 〉	통과 (1.60ms, 10.3MB)
테스트 4 〉	통과 (2.02ms, 10.3MB)
테스트 5 〉	통과 (1.95ms, 10.3MB)
테스트 6 〉	통과 (2.84ms, 10.4MB)
테스트 7 〉	통과 (1.49ms, 10.4MB)
테스트 8 〉	통과 (2.43ms, 10.3MB)
테스트 9 〉	통과 (2.40ms, 10.2MB)
테스트 10 〉	통과 (2.25ms, 10.3MB)