[Java] 2208번 보석 줍기

1. 문제 링크 및 문제

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

2. 해결 방법 생각해보자 ...

• 1번부터 N번까지 보석이 놓여있는 곳 까지 M개 이상 연속으로 주울 때 최대합을 구해야하므로
• 누적합(sum)을 구해서 max (sum[현재위치]-sum[현재위치-M] , dp[현재위치-1]+arr[현재위치])
  -> sum[현재위치]-sum[현재위치-M] : 현재위치로 부터 M개를 주웠을 경우
  -> dp[현재위치-1]+arr[현재위치] : 연속하여 M개이상 주은 경우
• 이해 안되면 바로 예시 적용 !!

🔴 예시로 이해하자 (백준예시)
예제 입력 1
8 4
-1
-1
1
1
1
1
-1
2
예제 출력 1
5

⭕️풀이

1. 배열 arr 와, 누적합 sum, dp 생성 (N+1 로 생성)
2. 최소 M 개 이상 주워야하므로, dp[M] = sum[M] 부터 시작
   = 최소 4개 이상 주워야하므로, dp[4] = sum[4]
   
3. dp[5] 값 구하기 == 현재위치 : 5
   

이렇게 연속으로 계속 줍는 합 vs 현재값-M 부터 현재값 까지를 더했을 때의 합 을 비교

4.dp[6]도 해보자

5. dp[7]

6. dp[8]

하여, 보석 5개를 훔칠 수 있음~
보석이 음수인 경우도 있으니, 아예 안훔치는 경우도 고려해야함

3. 코드

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

public class Main {

	static int N, M;
	static int[] arr, sum, dp;

	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		String[] input = br.readLine().split(" ");
		N = Integer.parseInt(input[0]);
		M = Integer.parseInt(input[1]);

		arr = new int[N + 1];
		sum = new int[N + 1];
		dp = new int[N + 1];

		for (int i = 1; i < N+1; i++) {
			arr[i] = Integer.parseInt(br.readLine());
			sum[i] = sum[i - 1] + arr[i]; // 누적합 구하기
		}

		dp[M] = sum[M];
		int maxResult = dp[M];

		for(int i=M+1;i<N+1;i++){
			dp[i] = Math.max(dp[i-1]+arr[i], sum[i]-sum[i-M]);
			maxResult = Math.max(maxResult, dp[i]);

		}
		if(maxResult<0 ) maxResult = 0;

		bw.write(maxResult + "\n");
		bw.flush();
	}
}

!

나는 DP가 너무너무 어렵다...
똑같은 방식을 다르게 적용하여 점화식을 세우는 간단한 원리같은데 .. 아직 익숙치 않아서 그런 듯
쉬워질 때 까지 문제 맨날 풀어봐야지.
계속 풀다보면 이걸 왜 어려워했지 라는 날이 올거라는 분명한 믿음이 있기에
화이팅!!~~