1757 달려달려 (java)

이 문제는 dp문제이다.

어떻게 알았나? ( 최소,최대값을 구하라는 키워드, 최적해를 구성하는 작은 문제역시 최적해다. 라는 최적부분 문제 구조를 띔) -> dp문제를 계속 풀다보면 보인다..

 

dp 문제는 점화식만 나오면 참 간단한데, 점화식을 끌어내기가 참 어렵다. 

 

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

이 문제는 knapsack (배낭) 문제 풀이와 유사하다. 

 

난 어디까지 접근했나. (M=1 의 점화식 까지만 구했다.)

M=1 일때의 점화식은 구했다. 하지만, 그 이상 접근법이 익숙치 않아 답을 찾게 되었다. 

M=1 의 점화식은 

if(N>=2) {
	dp[2]=arr[1]; 
}
for (int i = 3; i <= N; i++) {
	dp[i]=Math.max(dp[i-1], arr[i-1]+dp[i-2]); 
}

dp[n]의 정의 부터 해야한다. 

dp[n]은 n까지의 최선의 방법으로 달려왔고, 그렇게 n까지 왔을때, 지침지수가 0인 상태로 정의를 해놓는다. 

 

현재 n 를 기준으로 이전(n-1) 에 달리기를 선택했나 , 안했나 로 dp[n]의 후보를 고를 수있다.

선택 했냐 (arr[i-1] +dp[i-2]) : 선택 했으니, arr[i-1]을 더하고(지침지수+1) ( n때는 쉰다.(지침지수-1) ) , n-2 까지는 최선의 해를 더한다. dp[i-2]가 지침지수 0인 상태로 정의 했기 때문에 가능하다.(지침지수:0)  

선택 안 했냐 (dp[i-1]) 

 

dp[i-1] 의 경우가 선택되는 경우는 arr[i-2]를 무조건 선택해야될때 일어난다. 

아래 예시의 최댓값은 31 이다. 그러려면 

 

1	1	30	1	1
O	X	O	X	X

만약 arr[i-1]과 arr[i-2] 둘다 선택할 경우 n 시점에서 지침지수가 최소 1이되므로 안된다.

고로, arr[i-2]를 선택하기위해 dp[i-1]시점에서 고려하는 Math.max(arr[i-2]+dp[i-3],dp[i-2]) 을 위해 

dp[i-1]을 dp[n]을 구할때, 비교대상으로 넣어야한다.

 

하지만, 이는 아래와 같은 케이스에는 취약하다. 

7 3

10 

20

30

1

1

1

10

10	20	30	1	1	1	10
O	O	O	X	X	X	X

M에 따라서, 연속으로 몰아서 선택하는 경우가 있을 수 있다. 

이를 위해 knapsack 풀이를 적용한다.

 

 

2u_my_light 님의 코드를 참조하였다.

 

 

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

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader bf =new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st=new StringTokenizer(bf.readLine());
		int N=Integer.parseInt(st.nextToken());
		int M=Integer.parseInt(st.nextToken());
		int[] arr = new int[N + 1];
		 for (int i = 1; i <= N; i++) {
				arr[i]=Integer.parseInt(bf.readLine());
			}
		int[] psum = new int[N + 1];
		for (int i = 1; i <= N; i++) {
			psum[i] = psum[i - 1] + arr[i];
		}
		int[] dp = new int[N + 2];
		for (int i = 1; i <= N + 1; i++) {
			dp[i] = Math.max(dp[i], dp[i - 1]);
			for (int j = 1; j <= M && i + 2 * j <= N + 1; j++) {
				dp[i + 2 * j] = Math.max(dp[i + 2 * j], dp[i] + psum[i + j - 1] - psum[i - 1]);
			}
		}

		System.out.println(dp[N + 1]);
		
	}

}