[백준/java] 1757번 - 달려달려

[ 문제 ]

 

 

[ 구현 ]

 

잘 모르겠어서 gpt한테 힌트달라고 했는데도 점화식 이해하는데 좀 애먹었다..

힌트보고 이해한 다음에 코드는 손수 짰는데, 배열 크기 관련해서 신경써줘야하는 부분이 좀 있어서 디버깅하면서 고쳤다.

 

dp[i] = 시각 i부터 N까지 시작할 때 얻을 수 있는 최대 거리 (이때 지침 지수는 0)로 잡고

누적합을 통해 필요한 구간의 합을 계산하였다.

이때 필요한 구간의 합이란 연속으로 달릴 구간을 의미한다(i ~ i + L - 1)

dp자체가 bottom-up 방식이 아니라 top-down 방식으로 내려가는 형식이며

L이 가지는 제한 조건 -> L <= (n - i + 1) / 2를 반영해주면 된다.(끝날때 지침 지수가 0이려면 구간의 절반을 넘게 달릴 순 없음)

 

최종적으로 핵심이 되는 점화식은

dp[i] = Math.max(dp[i+1], sum(i ~ i + L - 1) + dp[i+2L])이다.

 

우선 dp[i+1]은 이전까지 구했던 값이 더 큰 경우 현상유지를 위한 기본 코드이며

i부터 시작해서 L만큼 달렸을때의 거리를 누적합을 통해 O(1)을 통해 계산하였다.

추가적으로 2L의 의미는 L 구간만큼 연속으로 달리면 다시 L구간만큼 쉬어줘야하기 때문에 그 부분이 반영되었다.

 

다만 L값이 증가함에 따라 값이 바뀌는 부분도 기록을 해줘야하기 때문에 Math.max(dp[i], ...)를 한번 더 감싸주었다.

 

+) 또한 dp[i + 2 * j]에서 인덱스가 n + 1까지 도달하는 경우 발생하기 때문에 arrayIndexOutOfBoundError가 터질 수 있어, 크기를 의도적으로 n + 2로 잡아주었다.

 

 

[ 코드 ]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

// dp[i] = 시각 i부터 N까지 시작할 때 얻을 수 있는 최대 거리 (이때 지침 지수는 0)
public class Main {

    static int[] dp;
    static int n, m;
    static int[] dist;
    static int[] prefixDist;
    static int answer;
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    private static void readInput() throws IOException{
        String input = br.readLine();
        String[] arr = input.split(" ");
        n = Integer.parseInt(arr[0]);
        m = Integer.parseInt(arr[1]);

        dist = new int[n + 2];
        prefixDist = new int[n + 1];
        dp = new int[n + 2];
        
        for (int i = 1; i <= n; i++) {
            input = br.readLine();
            dist[i] = Integer.parseInt(input);
            prefixDist[i] = prefixDist[i - 1] + dist[i];
        }
    }

    private static void dp() {
        for (int i = n - 1; i >= 1; i--) {
            for (int j = 1; j <= (n - i + 1) / 2; j++) {
                // i부터 L거리만큼 연속으로 달린 경우 거리 계산(누적합 배열을 이용해 N(1)으로)
                int distSum = prefixDist[n] - prefixDist[i - 1] - (prefixDist[n] - prefixDist[i + j - 1]);
                dp[i] = Math.max(dp[i], Math.max(dp[i + 1], distSum + dp[i + 2 * j]));
            }
        }

        answer = dp[1];
    }

    private static void solution() throws IOException {
        readInput();
        dp();
        System.out.println(answer);
    }

    public static void main(String[] args) throws IOException {
        Main.solution();
    }
}

 

 

[ 마무리 및 느낀 점 ]

 

개인적으로 골드4이지만 간단히 풀기는 어려운 느낌의 dp인 것 같다.

dp 관련해서 좀 더 공부를 하고 다양한 케이스를 접하며 기본 이해도를 높여야겠다.

같은 문제를 2차원 dp, 3차원 dp로 풀 수 있는 것 같던데 한번 시도해볼 예정이다.