06. 최대점수 구하기

 

설명

최대점수구하기

 

 

예시

5 20
10 5
25 12
15 8
6 3
7 4

 

41

 

 

 

 

풀이

 

맨 뒤부터 돌면서 해당숫자-time[i]인 곳에가서 내 score을 더한후 더 큰값을 배열에다가 넣어준다.

 

for(int i=0; i<n; i++) {
     for(int j=m; j>=time[i]; j--) {
         dis[j]=Math.max(dis[j], dis[j-time[i]]+score[i]);
     answer=Math.max(answer, dis[j]);
   }
}

import java.util.*;


class Main {
	
	public static void main(String[] args){
		
		Scanner sc= new Scanner(System.in);
		
		int n= sc.nextInt();
		int m= sc.nextInt();
		
		int[] score= new int[n];
		int[] time= new int[n];
		
		for(int i=0; i<n ; i++) {
			int s= sc.nextInt();
			int t= sc.nextInt();
			score[i]=s;
			time[i]=t;
		}
		
		int[] dis = new int[m+1];
		Arrays.fill(dis, 0);
		
		int answer=0;
		
		for(int i=0; i<n; i++) {
			for(int j=m; j>=time[i]; j--) {
				dis[j]=Math.max(dis[j], dis[j-time[i]]+score[i]);
				answer=Math.max(answer, dis[j]);
			}
		}
		
		System.out.println(answer);

	}

	
}