[Gold V] 벼락치기 - 14728

문제 링크

성능 요약

메모리: 18232 KB, 시간: 132 ms

분류

다이나믹 프로그래밍, 배낭 문제

제출 일자

2024년 8월 5일 06:02:57

문제 설명

ChAOS(Chung-ang Algorithm Organization and Study) 회장이 되어 일이 많아진 준석이는 시험기간에도 일 때문에 공부를 하지 못하다가 시험 전 날이 되어버리고 말았다. 다행히도 친절하신 교수님께서 아래와 같은 힌트를 시험 전에 공지해 주셨다. 내용은 아래와 같다.

1. 여러 단원을 융합한 문제는 출제하지 않는다.
2. 한 단원에 한 문제를 출제한다. 단, 그 단원에 모든 내용을 알고 있어야 풀 수 있는 문제를 낼 것이다.

이런 두가지 힌트와 함께 각 단원 별 배점을 적어 놓으셨다. 어떤 단원의 문제를 맞추기 위해서는 그 단원의 예상 공부 시간만큼, 혹은 그보다 더 많이 공부하면 맞출 수 있다고 가정하자. 이때, ChAOS 회장 일로 인해 힘든 준석이를 위하여 남은 시간 동안 공부해서 얻을 수 있는 최대 점수를 구하는 프로그램을 만들어 주도록 하자.

입력

첫째 줄에는 이번 시험의 단원 개수 N(1 ≤ N ≤ 100)과 시험까지 공부 할 수 있는 총 시간 T(1 ≤ T ≤ 10000)가 공백을 사이에 두고 주어진다.

둘째 줄부터 N 줄에 걸쳐서 각 단원 별 예상 공부 시간 K(1 ≤ K ≤ 1000)와 그 단원 문제의 배점 S(1 ≤ S ≤ 1000)가 공백을 사이에 두고 주어진다.

출력

첫째 줄에 준석이가 얻을 수 있는 최대 점수를 출력한다.

풀이 - DP(배낭문제)

배낭 문제의 기초 정도 문제라고 볼 수 있다.

흔히 배낭 문제라고 하면

//무게가 최대 배낭 무게를 초과할 경우
dp[N][W] = dp[N-1][W];

//무게를 초과하지 않을 경우
dp[N][M] = Math.max(dp[N-1][M],dp[N-1][M - 물건무게] + 물건 가치);

위 두가지 경우를 고려해주는 것이 일반적인데, 이를 그대로 따라가는 문제이다.

따라서 어렵다기보다는 배낭 문제에 익숙해지기 위한 문제라고 생각한다.

혹시나 배낭 문제 푸는 방식에 대해 잊어버렸거나, 잘 모를 경우 이를 정리해준 블로그 [배낭 문제 이해하기]를 참고하도록 하자!

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main{
	//dp - 배낭문제
	static int N,T; //단원 개수 , 총 시간
	static int[][] item; //단원 별 예상 공부 시간과 배점을 담은 배열
	static int[][] dp;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		T = Integer.parseInt(st.nextToken());
		
		item = new int[N+1][2];
		dp = new int[N+1][T+1];
		
		for(int i=1; i<=N; i++) {
			st = new StringTokenizer(br.readLine());
			item[i][0]=Integer.parseInt(st.nextToken()); //단원 별 예상 공부 시간
			item[i][1]=Integer.parseInt(st.nextToken()); //배점
		}
		
		for(int i=1; i<=N; i++) {
			for(int j=1; j<=T; j++) {
				if(item[i][0] > j) { //만약 현재 시간보다 예상 공부 시간이 더 크다면?
					dp[i][j] = dp[i-1][j];
				}
				else {
					dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-item[i][0]]+item[i][1]);
				}
			}
		}
		
		System.out.println(dp[N][T]);
	}
}