[BOJ] 30464. 시간낭비 (🥇, 그래프 DP)

🔗

풀이

바라보는 방향은 딱 2번 회전할 수 있고, 처음 바라보고 있는 방향은 오른쪽으로 고정이다. 즉 오른쪽 -> 왼쪽 -> 다시 오른쪽, 이렇게 3가지 경우만 존재하게 된다.

주어지는 예제들은 세 가지 경우를 구분하지 않고 계산해도 제대로 된 정답이 나올 수 있지만 실제로는 모든 가능한 경우에 대해 고려해야 한다. 하지만 N이 20만이기 때문에 아예 완전 탐색은 불가능하고 적절하게 DP를 사용해야 한다.

모든 위치에 대해 아래와 같이 세 경우가 존재하게 된다.

1. 오른쪽
2. 한 번 방향 바꾼 왼쪽
3. 두 번 방향 바꿔서 다시 오른쪽

만약 시작 위치 1에 있다고 하면 여기서는 바라보고 있는 방향으로 1칸 이동하게 된다. 이때까지는 방향을 한 번도 바꾸지 않았으므로 방향을 바꿀 기회가 존재한다. 결국 현재 방향으로 직진하거나, 방향을 바꿔서 직진하는 두 가지 경우가 존재하게 된다.

1번은 현재 방향으로의 직진, 2번은 방향 바꿔서 직진이다. 결국 방향을 바꿀때마다 1행씩 내려가게 되고, 1번 행에서는 직진을 할 때 현재 위치에서 위치값을 빼주기만하면 된다.

2번 행에 도달하게 되면 더 이상 방향을 바꿀 수 없으므로 직진만 가능하다.

최대값을 구해야 하기 때문에 모든 값의 초기화 값을 Integer.MIN_VALUE로 해주어야 한다. 이때 같은 위치를 여러번 방문하게 될 수도 있는데 이미 방문한 위치에서 얻을 수 있는 값은 중복되기 때문에 한 번 방문한 곳이라면 두 번 방문하지 않을 수 있도록 해야 한다.

그래서 처음 초기화 값은 -1로 설정하고, 만약 해당 노드에 방문했는데 값이 -1이 아니면 이미 방문한 것이므로 저장된 값을 반환시키면 된다. 이때 초기화 값은 Integer.MIN_VALUE로 하지 않는 것은 이 노드에 방문할 경우의 수가 존재하지 않는 경우 해당 값이 그대로 저장되어 있기 때문이다. 만약 이 값을 현재 노드에 방문하지 않았다는 기준값으로 설정하게 되면 해당 노드에 방문할 수 있는 경우가 없는 것과 해당 노드에 방문한 적이 없는 것이 같은 방식으로 표현되기 때문에... 시간초과가 발생한다. 즉 이 노드에는 한 번도 방문한 적이 없어요~라는 뜻과 이 노드 방문해봤더니 방문할 방법이 없더라는 방문한것도 방문한 것도 아닌 충돌이 생긴다는 뜻.

그래서 초기화 값은 -1로 따로 설정해주는 게 좋다.

import java.util.*;
import java.io.*;

public class Main {
    static int[] pos;
    static int N;
    static int[][] dp;
    
    public static int f(int cur, int u) {
        if (cur < 0 || cur >= N) return Integer.MIN_VALUE;
        if (cur == N-1) return 0;
        if (dp[cur][u] != -1) return dp[cur][u];
        
        dp[cur][u] = Integer.MIN_VALUE;
        if (u == 0) {
            dp[cur][u] = Math.max(f(cur + pos[cur], u), f(cur - pos[cur], u+1)) + 1;
        } else if (u == 1) {
            dp[cur][u] = Math.max(f(cur - pos[cur], u), f(cur + pos[cur], u+1)) + 1;
        } else {
            dp[cur][u] = f(cur + pos[cur], u) + 1;
        }

        return dp[cur][u];
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        pos = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            pos[i] = Integer.parseInt(st.nextToken());
        }
        
        dp = new int[N][3];
        for (int i = 0; i < N; i++) {
            Arrays.fill(dp[i], -1);
        }

        // dp[0][0] = 0;
        int answer = f(0, 0);
        System.out.println(answer > 0 ? answer : -1);
    }
}