최대점수 구하기(Dynamic Programing)

최대점수 구하기

 

 

 

 

코드

package dynamic;

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

/**
 * 최대점수 구하기(냅색 알고리즘)
 */
public class Dynamic5 {


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");

        int N = Integer.parseInt(str[0]); // 문제의 개수
        int M = Integer.parseInt(str[1]); // 풀이 시간

        int[] dy = new int[M + 1]; // 각 인덱스는 시간

        StringTokenizer st;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());

            int ps = Integer.parseInt(st.nextToken());
            int pt = Integer.parseInt(st.nextToken());

            for (int j = M; j >= pt; j--) {
                dy[j] = Math.max(dy[j], dy[j - pt] + ps);
            }
        }

        System.out.println(dy[M]);
    }
}

 

※ 풀이

• 동전 교환처럼 자원이 무한정 있는 경우는 j가 앞에서 부터 움직이고, 위 문제처럼 개수가 유한정 정해진 경우 j는 뒤에서 부터 움직인다. (중복 제거 위해)
• dy[ j ]는 j 분 동안 풀 수 있는 최대 점수를 저장한다.