[BaekJoon] 14728 벼락치기 (Java)

1.  문제 링크

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

2.  문제

요약

• 교수님께서 아래와 같은 힌트를 시험 전에 공지해 주셨습니다.
  • 여러 단원을 융합한 문제는 출제하지 않습니다.
  • 한 단원에 한 문제를 출제하는데, 그 단원에 모든 내용을 알고 있어야 풀 수 있는 문제를 냅니다.
• 위 두가지 힌트와 함께 각 단원별 배점 또한 주어졌습니다.
• 어떤 단원의 문제를 맞추기 위해서는 그 단원의 예상 공부 시간만큼, 혹은 그보다 더 많이 공부하면 맞출 수 있다고 가정합니다.
• 남은 시간 동안 공부해서 얻을 수 있는 최대 점수를 구하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 100보다 작거나 같은 시험의 단원 개수 N과 1보다 크거나 같고 10000보다 작거나 같은 공부할 수 있는 총 시간 T가 주어지고 두 번째 줄부터 N개의 줄에는 1보다 크거나 같고 1000보다 작거나 같은 각 단원별 예상 공부 시간 K와 1보다 크거나 같고 1000보다 작거나 같은 그 단원 문제의 배점 S가 주어집니다.
• 출력: 첫 번째 줄에 얻을 수 있는 최대 점수를 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
	public int getMaxScore(int t, Unit[] units) {
		int[] dp = new int[t + 1];
		for(int i = 0; i < units.length; i++) {
			for(int j = t; j >= units[i].time; j--) {
				dp[j] = Math.max(dp[j], dp[j - units[i].time] + units[i].score);
			}
		}
		return dp[t];
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String[] input = br.readLine().split(" ");
		int n = Integer.parseInt(input[0]);
		int t = Integer.parseInt(input[1]);
		Unit[] units = new Unit[n];
		for(int i = 0; i < n; i++) {
			input = br.readLine().split(" ");
			units[i] = new Unit(Integer.parseInt(input[0]), Integer.parseInt(input[1]));
		}
		br.close();
		Main m = new Main();
		bw.write(m.getMaxScore(t, units) + "\n");
		bw.flush();
		bw.close();
	}
	
	public static class Unit {
		int time;
		int score;
		public Unit(int time, int score) {
			this.time = time;
			this.score = score;
		}
	}
}

4.  접근

• 해당 문제는 DP를 이용하여 구할 수 있는 문제입니다.
• 공부할 수 있는 시간이 각 시간일 때 얻을 수 있는 최대 점수를 나타내는 배열 dp를 생성합니다.
• 공부할 수 있는 시간이 t초일 때부터 각 단원의 예상 공부 시간일 때까지 각 단원을 공부할 수 있으므로 각 단원의 예상 공부 시간까지 각 단원 문제의 배점으로 dp 배열을 채웁니다.
• 이 때, 이전에 어떠한 단원으로라도 이미 dp 배열이 채워져있다면, 현재 단원 문제의 배점과 dp에서 (현재 공부할 수 있는 시간 - 현재 단원 예상 공부 시간)의 값을 더한 값과 dp에서 현재 시간일 때의 값을 비교하여 더 큰 값을 dp에서 현재 시간일 때의 값으로 변경합니다.
  • dp[time] = Math.max(dp[time], dp[time - unit_time] + unit_score)
    • time: 현재 공부할 수 있는 시간
    • unit_time: 단원의 예상 공부 시간
    • unit_score: 단원 문제의 배점
• 모든 단원에 대해서 확인하고 난 후에 dp[t]의 값이 얻을 수 있는 최대 점수가 됩니다.