import java.util.Scanner;
public class Main{
public static void main(String[] args) {
Scanner kb = new Scanner(System.in);
int n = kb.nextInt(); // 문제의 개수
int m = kb.nextInt(); // 주어진 시간
int[] dp = new int[m+1]; // dp[i] = i분 동안 풀 수 있는 최대 점수
for(int i=0; i<n; i++){
int score=kb.nextInt(); // 점수
int time=kb.nextInt(); // 시간
for(int j=m; j>=time; j--){
dp[j] = Math.max(dp[j], dp[j-time]+score); // 최대 점수 갱신
}
}
System.out.println(dp[m]); // m분 동안의 최대 점수
}
}
이 전 동전 교환 문제와 비슷하지만 썼던 동전을 또 쓸 수 있는 동전교환 문제와 달리
이 문제는 같은 문제를 또 풀 수 없다. 그렇기에 이중 for문을 돌 때 j가 뒤에서 거꾸로 돌며 입력받은 시간만큼을 빼준 dp[j-time]과 비교한다.
'ALGORITHM' 카테고리의 다른 글
[JAVA] 백준 13398번- 연속합 2 (0) | 2022.11.11 |
---|---|
[JAVA] 백준 17404번- RGB거리2 (0) | 2022.11.09 |
[JAVA] 알고리즘 : 동적 계획법- 동전교환(냅색 알고리즘) (0) | 2022.11.09 |
[JAVA] 백준 9465번- 스티커 (0) | 2022.11.08 |
[JAVA] 백준 11054번- 가장 긴 바이토닉 부분 수열 (0) | 2022.11.07 |