[알고리즘]백준 1757: 달려달려

 

 

풀이 과정

memo[n][m]에 저장할 값은 시간 n에 지침 정도 m일 때 가질 수 있는 최댓값이다.

 

• 쉬는 경우 (memo[n][0] = memo[n-1][0]): 이전 시간의 최대 거리를 그대로 유지.
• 뛰는 경우 (memo[n][m] = memo[n-1][m-1] + D[n]): 이전 시간까지 뛴 거리에서 현재 거리를 더하여 최대 거리 갱신.
• 마지막으로 최대 연속 시간 M 이내에서 쉬는 경우를 비교하여, 특정 시간에 쉬었을 때의 최대 거리를 갱신.

 

 

코드

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

// dp
public class Main_1757_G4_달려달려 {
    public static int N,M;
    public static int[] D;
    public static int[][] memo; //시간 n에 지침정도 m일 때 최대값

    public static void main(String[] args) throws Exception{
        // 1. 입력 및 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        D = new int[N];
        for(int i=0; i<N; i++){
            D[i] = Integer.parseInt(br.readLine());
        }
        memo = new int[N][M+1];
        memo[0][1] = D[0];

        // 2. dp - bottom up
        for(int n=1; n<N; n++){
            memo[n][0]=memo[n-1][0];

            for(int m=1; m<=M; m++){
                memo[n][m]=memo[n-1][m-1]+D[n];
            }

            for(int i=1; i<=M & i<=n; i++){
                memo[n][0]=Math.max(memo[n][0], memo[n-i][i]);
            }
        }

        // 3. 출력
        System.out.println(memo[N-1][0]);
    }
}

 

 

출처

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