[BOJ/백준] 31413 - 입대

 

31413번: 입대

---

2차원 DP

 

헌혈 횟수와 일수

---

---

• 제목

입대

---

• 조건

시간 제한 : 1 초

메모리 제한 : 1024 MB 

---

• 문제

드디어 병역의 의무를 질 나이가 된 용진이는 선진병영을 선도하는 대한민국 공군병 모집에 지원하고자 한다. 대한민국 공군 모집병으로 합격하기 위해선 가산점이 필요한데, 최근 높아진 공군의 인기 탓에 봉사활동 혹은 헌혈을 통해 
M점 이상의 가산점을 모아야 한다.

현재 공군 지원일까지는 N일이 남았으며, 그중 i일에는 si점의 가산점을 얻을 수 있는 봉사활동에 참여할 수 있다. 헌혈은 
1일부터 N일까지 아무 날짜에 할 수 있으며, 헌혈하는 경우 A점의 가산점을 획득한다. 단, 헌혈을 하는 경우 충분한 휴식을 위해 헌혈한 날을 포함하여 헌혈 이후 D일 동안 헌혈하거나 봉사활동에 참여할 수 없다.

헌혈이 무서웠던 용진이는 헌혈을 최대한 적게 하며 가산점을 M점 이상 모으고자 한다. 용진이를 도와 공군병 모집 마감일까지 M점 이상의 가산점을 모으기 위한 최소 헌혈 횟수를 구해주자.

---

• 입력

첫 번째 줄에 공군병 모집 마감일까지 남은 날짜 N과 합격하는 데 필요한 가산점을 의미하는 정수 M이 공백으로 구분되어 주어진다. (1 ≤ N ≤ 1,000,1 ≤ M ≤ 10^7)

두 번째 줄에 날짜마다 봉사활동에 참여해 얻을 수 있는 가산점을 의미하는 N개의 정수 s1 ... sN이 공백으로 구분되어 주어진다. (1 ≤ si ≤ 1,000)

세 번째 줄에 헌혈해서 얻을 수 있는 가산점을 의미하는 정수 A와 헌혈 후 휴식이 필요한 일수 D가 공백으로 구분되어 주어진다. (1 ≤ A ≤ 10,000, 1 ≤ D ≤ N)

---

• 출력

최소 M점 이상의 가산점을 모으기 위해 필요한 최소 헌혈 횟수를 출력한다.

어떻게 해도 M점 이상의 가산점을 모을 수 없다면, -1을 출력한다.

---

예제 입력1	예제 출력1
5 34 1 4 8 6 3 10 2	2

 

예제 입력1	예제 출력1
4 21 3 5 4 6 8 2	-1

---

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

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer st;

	public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());

		st = new StringTokenizer(br.readLine());
		int[] s = new int[10000 + 1000 + 1];
		int[][] dp = new int[(1000 + 1) + 1][10000 + 1000 + 1];
		for (int i = 1; i <= N; i++) {
			s[i] = Integer.parseInt(st.nextToken());
			dp[0][i] = dp[0][i - 1] + s[i];
		}

		st = new StringTokenizer(br.readLine());
		int A = Integer.parseInt(st.nextToken());
		int D = Integer.parseInt(st.nextToken());

		int answer = Integer.MAX_VALUE;
		for (int i = 0; i <= N / D + 1; i++) {
			for (int j = D; j < N + D; j++) {
				if (i > 0) {
					dp[i][j] = Math.max(dp[i][j - 1] + s[j], dp[i - 1][j - D] + A);
				}
				if (dp[i][j] >= M) {
					answer = Math.min(answer, i);
				}
			}
		}
		System.out.print(answer == Integer.MAX_VALUE ? -1 : answer);
	}
}