[백준 31671] 특별한 오름 등반 [Java]

문제

http://boj.ma/31671

31671번: 특별한 오름 등반

 

---

풀이

문제 요약

출발점에서 도착점까지 주어진 규칙대로 이동하면서, 최대한 높게 도달할 수 있는 y를 구하자.

아이디어

출발점과 도착점으로부터 선생님을 피하며, 모든 가능한 영역을 가보자. 이후 두 탐색에 대한 교차점 중 y가 가장 높은 경우를 찾으면 된다.

점화식은 다음과 같다.

dp[D][x][y] : D(출발점 또는 도착점)에서 출발했을 때 (x, y)에 도달할 수 있는지 여부

        // Solve
        boolean[][][] dp = new boolean[2][WIDTH][HEIGHT];
        int[] D = new int[] {-1, 1};
        dp[L][0][0] = true;
        for (int x = 0; x < WIDTH - 1; ++x) {
            for (int y = 0; y <= HEIGHT - 1; ++y) {
                if (!dp[L][x][y]) {
                    continue;
                }
                for (int dy : D) {
                    final int nx = x + 1;
                    final int ny = y + dy;
                    if (isValid(nx, ny) && !forbidden[nx][ny]) {
                        dp[L][nx][ny] = true;
                    }
                }
            }
        }
        dp[R][2*N][0] = true;
        for (int x = WIDTH - 1; x >= 1; --x) {
            for (int y = 0; y <= HEIGHT - 1; ++y) {
                if (!dp[R][x][y]) {
                    continue;
                }
                for (int dy : D) {
                    final int nx = x - 1;
                    final int ny = y + dy;
                    if (isValid(nx, ny) && !forbidden[nx][ny]) {
                        dp[R][nx][ny] = true;
                    }
                }
            }
        }

        int maxY = -1;
        for (int x = 0; x < WIDTH; ++x) {
            for (int y = 0; y < HEIGHT; ++y) {
                if (dp[L][x][y] && dp[R][x][y]) {
                    maxY = Math.max(maxY, y);
                }
            }
        }

풀이 시간

20분

---

소스코드

https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/normal/31671.java

problem-solving/baekjoon-online-judge/normal/31671.java at main · rogi-rogi/problem-solving