글 읽기 - 반례 부탁 드립니다.

spire99 5년 전 0

각 칸의 값이 절대값 100을 넘지 않기 때문에, 지나간 칸을 의미해서 999를 넣고, 왼쪽,오른쪽,아래로만 탐색하고, long형을 이용하여 range도 보정했는데

9%에서 틀렸다고 나오네요. 반례 혹은 이상한 점 조언 부탁 드립니다.

dpValue는 -inf로 초기화된 상태 입니다.

public static long calc(int x, int y) {
        if(x==N-1 && y==M-1){
            return sArr[N - 1][M - 1];
        }

        long ret = -inf;

        if (dpValue[x][y] != -inf) {
            return dpValue[x][y];
        }

        int val = sArr[x][y];
        if (y - 1 >= 0 && sArr[x][y - 1] != 999) {
            sArr[x][y] = 999;
            ret = val + calc(x, y - 1);
            sArr[x][y] = val;
        }

        if (y + 1 < M && sArr[x][y + 1] != 999) {
            sArr[x][y] = 999;
            ret = Math.max(ret, val + calc(x, y + 1));
            sArr[x][y] = val;
        }

        if (x + 1 < N && sArr[x + 1][y] != 999) {
            sArr[x][y] = 999;
            ret = Math.max(ret, val + calc(x + 1, y));
            sArr[x][y] = val;
        }

        dpValue[x][y] = ret;
        return ret;

    }

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례 부탁 드립니다.

spire99 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말