[백준 30464] 시간 낭비 - Java 문제풀이

문제 링크: https://www.acmicpc.net/problem/30464

 

 

문제

건덕이는 학교에 가기 너무 싫은 나머지 최대한 늦게 학교에 도착하려고 한다. 등굣길은 N개의 칸이 가로로 놓인 형태이며, 각 칸은 가장 왼쪽 칸부터 오른쪽으로 1부터 N까지 번호가 매겨진다. 건덕이는 1번 칸에, 학교는 N번 칸에 존재한다.

건덕이는 처음에 학교를 바라보는 방향으로 서 있다. 등교하는 방법은 특이한데, 1분마다 현재 자신이 서 있는 칸에 쓰인 수만큼 바라보는 방향으로 이동한다. 이때, 등굣길을 벗어나도록 이동할 수 없다.

건덕이는 바라보는 방향을 최대 두 번 반전할 수 있다. 학교가 있는 칸에 처음으로 도착하는 시간을 최대한 늦추면 출발 몇 분 뒤에 도착할까? 건덕이가 방향을 반전하는 데 드는 시간은 무시한다.

 

입력

첫 번째 줄에 학교가 있는 칸의 번호 N이 주어진다. (3 ≤ N ≤ 200000)

두 번째 줄에 각 칸에 쓰인 정수 ai가 공백으로 구분되어 주어진다. (0 ≤ ai ≤ 200 000)

 

출력

건덕이가 최대한 시간을 끈 뒤, 학교가 있는 칸에 처음으로 도착하는 시간을 출력한다. 학교에 도착할 수 있는 경로가 없다면 -1을 출력한다.

풀이

접근법

1. 해당 지점에서 뒤로 갔을 때 갈 수 있는 최대 거리수를 구하면 될 것 같다.
2. 해당 지점에서 뒤로 갔을 때 최대 거리수는, 해당 지점에서 뒤로 간 지점에서 더 뒤로 갈건지, 그 지점에서 앞으로 갈건지 비교하면 될 것 같다.
3. 처음에, 해당 지점에서 더 갈 수 있는지 체크는, i=N-1 ~ i=0까지 돌면서 한칸 더 갔을 때 지점을 넘어가면 -1이고, 그렇지 않으면 더 갔을 경우 + 1이 될 것이다.
4. 처음부터 돌면서, 한칸씩 더 갔을 때 해당 지점까지 간 거리 + 뒤로 갔을 때의 최대값을 해서 이 값들의 최대값이 정답이 된다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

// 11:15 ~
public class Main {
    private static int N;
    private static int[] arr;
    private static int[][] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N=Integer.parseInt(br.readLine());
        arr = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0;i<N;i++) arr[i] = Integer.parseInt(st.nextToken());
        // [0]: 해당 칸에서 N 까지 가는 경로 수
        // [1]: 해당 칸에서 백했을 때 몇칸 갈 수 있는지
        dp = new int[2][N];
        for(int i=0;i<2;i++) Arrays.fill(dp[i], -1);
        dp[0][N-1] = 0;
        // 해당 지점에서 N 번째 칸을 갈 수 있는지 체크
        for(int i=N-2;i>=0;i--) {
            int nxt = i + arr[i];
            // 만약 더 갔을 때 N칸을 벗어나거나, 더 갔을 때의 값도 N칸은 못가면 -1이 유지됨
            if (nxt >= N || dp[0][nxt] == -1) continue;
            dp[0][i] = dp[0][nxt] + 1;
        }

        dp[1][0] = -1;
        // 해당 칸에서 뒤로 백했을 때 최대값
        for(int i=1;i<N;i++) {
            int back = i - arr[i];
            if (back < 0) continue;
            if (dp[0][i] == -1 && dp[0][back] == -1 && dp[1][back] == -1) continue;
            dp[1][i] = Math.max(dp[0][i], Math.max(dp[0][back], dp[1][back]) + 1);
        }

        int now = 0;
        int ans = dp[0][0];
        int cnt = 0; // 1번칸 ~ now 까지 일자로 갔을 때의 시간
        while(true) {
            if (now >= N-1) break;
            if (dp[0][now] == -1 && dp[1][now] == -1) {
                if (arr[now] == 0) break; // 0 이라는 것은 더 갈 수 없는 상황이라 종료되어야 한다.
                now += arr[now];
                cnt++;
                continue;
            }
            ans = Math.max(ans, cnt + dp[1][now]);
            if (arr[now] == 0) break;
            now += arr[now];
            cnt++;
        }
        System.out.println(ans);
    }
}

엄청 오래 걸렸다. 그래도 맨날 한눈에 봤을 때 풀리던 문제들만 풀었는데, 오랜만에 머리쓰는 문제를 풀어서 뿌듯하다.