[ BOJ ][JAVA][1757] 달려달려

https://www.acmicpc.net/problem/1757

1757번: 달려달려

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	1118	422	337	37.155%

문제

어제, 그리고 어제 어제 단체달리기를 두 번이나 하였다. 원장선생님의 이러한 하드 트레이닝으로 월드 학생들의 체력은 거의 박지성 수준이 되었다. 그래서 월드 학생들은 운동장을 도는데 정확히 N분에 완주할 수 있는 시간 안배능력까지 갖추게 되었다.

그래서 N분동안 학생들은 달릴지 아님 쉴지 결정하여야 한다. 그러나 학생들도 인간이기 때문에 계속 달릴 수는 없다. “지침 지수”라는 것이 있어서 1분을 달린다면 “지침 지수”는 1이 올라간다. 반대로 1분을 쉰다면 “지침 지수”는 1이 내려간다. 또한 이 “지침 지수”가 M보다 커지면 학생들은 더 이상 달릴 수가 없다.

아주 특이하게도 학생들은 시간에 따라 달릴 수 있는 거리가 다르다. 만약 I분에 달렸다면 Di 만큼의 거리를 달릴 수 있다. (i분을 달렸다는 것이 아니라 I분이 되는 때에 달렸다는 뜻임) 또한 학생들이 쉬기 시작하면 지침지수가 0이 되기 전에는 다시 달릴 수가 없다.

물론 이 달리기가 끝나면 학생들은 다시 공부를 해야한다. 그렇기 때문에 달리기가 끝난다음 지침지수가 0이 되지 않는다면 맑은 정신으로 문제를 풀 수가 없기 때문에 달리기가 끝나면 지침지수는 0이 되어야 한다.

월드학생들이 최대한 멀리 갈 수 있는 거리를 구해보자.

입력

첫째 줄에 운동할 시간 N(1 ≤ N ≤ 10000)과 M(1 ≤ M ≤ 500)이 주어진다. 이어서 N개의 줄에 i분에 달릴수 있는 거리 Di(0 ≤ Di ≤ 10,000)가 차례차례 주어진다.

출력

첫째 줄에 최대로 멀리 갈 수 있는 거리를 출력하라.

예제 입력 1

5 2
5
3
4
2
10

예제 출력 1

9

힌트

1분에 5만큼 뛰고 2분때 쉬고 3분에 뛰어서 4를 더 뛰고 4 5분은 쉰다.

접근

dp는 하면 할 수록 새롭다..

냅색 형태의 DP문제인 것은 알았지만 어떻게 디자인 해야 할지 감이 오지 않아

https://blog.naver.com/PostView.naver?blogId=kerochuu&logNo=222375177205&categoryNo=8&parentCategoryNo=0&viewDate=&currentPage=1&postListTopCurrentPage=1&from=postView를 참고했다.

코드

/**
 * BOJ 1757 달려달려 : Gold 4
 * DP
 */
import java.io.*;
import java.util.*;

public class p1757 {
    static int n, m;
    static int[] time;
    static int[][] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken()); // 한계 지침지수

        time = new int[n + 1];
        for (int i = 0; i < n; i++) {
            time[i + 1] = Integer.parseInt(br.readLine());
        }
        // dp[idx][지침지수] : 갈 수 있는 최대 거리
        dp = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            solution(i, time[i]);
        }
        System.out.println(dp[n][0]);
    }

    /**
     * idx번째에서의 거리는 사실상 idx-1번째의 상태에 의해서 결정된다.
     */
    static void solution(int idx, int move) {
        // idx번째에 쉬었을 경우
        dp[idx][0] = dp[idx - 1][0];

        // idx번째에 달렸을 경우
        for (int exh = 1; exh <= m; exh++) {
            dp[idx][exh] = dp[idx - 1][exh - 1] + move;
        }

        // 지침지수가 0으로 끝나는 경우의 최댓값을 저장
        for (int exh = 1; exh <= m && idx > exh; exh++) {
            // dp[idx-1][1] : 지침지수가 1로, 한 턴 쉰 애들
            // dp[idx-2][2] : 지침지수가 2로, 두 턴 쉰 애들
            dp[idx][0] = Math.max(dp[idx][0], dp[idx - exh][exh]);
        }
    }
}