728x90
문제
ChAOS(Chung-ang Algorithm Organization and Study) 회장이 되어 일이 많아진 준석이는 시험기간에도 일 때문에 공부를 하지 못하다가 시험 전 날이 되어버리고 말았다. 다행히도 친절하신 교수님께서 아래와 같은 힌트를 시험 전에 공지해 주셨다. 내용은 아래와 같다.
- 여러 단원을 융합한 문제는 출제하지 않는다.
- 한 단원에 한 문제를 출제한다. 단, 그 단원에 모든 내용을 알고 있어야 풀 수 있는 문제를 낼 것이다.
이런 두가지 힌트와 함께 각 단원 별 배점을 적어 놓으셨다. 어떤 단원의 문제를 맞추기 위해서는 그 단원의 예상 공부 시간만큼, 혹은 그보다 더 많이 공부하면 맞출 수 있다고 가정하자. 이때, ChAOS 회장 일로 인해 힘든 준석이를 위하여 남은 시간 동안 공부해서 얻을 수 있는 최대 점수를 구하는 프로그램을 만들어 주도록 하자.
입력
첫째 줄에는 이번 시험의 단원 개수 N(1 ≤ N ≤ 100)과 시험까지 공부 할 수 있는 총 시간 T(1 ≤ T ≤ 10000)가 공백을 사이에 두고 주어진다.
둘째 줄부터 N 줄에 걸쳐서 각 단원 별 예상 공부 시간 K(1 ≤ K ≤ 1000)와 그 단원 문제의 배점 S(1 ≤ S ≤ 1000)가 공백을 사이에 두고 주어진다.
출력
첫째 줄에 준석이가 얻을 수 있는 최대 점수를 출력한다.
풀이
배낭 문제를 이용하여 가장 가성비가 좋은 힌트를 공부한다.
마지막 시간에 저장된 값이 가장 가성비가 좋은 힌트이다.
코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n=Integer.parseInt(st.nextToken()), t=Integer.parseInt(st.nextToken());
int [] dp = new int [t+1];
for(int i=0;i<n;i++) {
st = new StringTokenizer(br.readLine());
int k, s;
k=Integer.parseInt(st.nextToken());
s=Integer.parseInt(st.nextToken());
for(int j=t;j>=k;j--) {
dp[j]=Math.max(dp[j], dp[j-k]+s);
}
}
System.out.println(dp[t]);
}
}
728x90
728x90
'Algorithm > Baekjoon' 카테고리의 다른 글
Baekjoon 10819 차이를 최대로 JAVA (1) | 2022.10.04 |
---|---|
Baekjoon 3060 욕심쟁이 돼지 JAVA (1) | 2022.10.04 |
Baekjoon 23881 알고리즘 수업 - 선택 정렬 1 JAVA (0) | 2022.09.28 |
Baekjoon 5893 17배 JAVA (0) | 2022.09.20 |
Baekjoon 5347 LCM JAVA (0) | 2022.09.18 |
댓글