[JAVA]백준 14728번: 벼락치기

www.acmicpc.net/problem/14728

14728번: 벼락치기

1. 문제 설명

 

준석이가 공부할 수 있는 총시간의 개수와 공부해야 하는 단원의 개수가 주어진다. 단원마다 단원의 문제를 맞히기 위해 필요한 공부시간과 점수가 주어진다고 하였을 때 준석이가 얻을 수 있는 최대 점수를 구하는 문제이다.

 

2. 풀이

 

간단한 DP 문제이다.

dp[x] = 공부할 수 있는 시간이 x일 때 준석이가 얻을 수 있는 최대 점수

 

시간 복잡도 O(NT) (N은 단원 개수, T는 준석이가 공부할 수 있는 총 시간)

 

3. 코드

import java.io.*;
import java.util.*;

public class Main {


    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int chapter_num, study_time, answer = 0;

        StringTokenizer input = new StringTokenizer(br.readLine());

        chapter_num = Integer.parseInt(input.nextToken());
        study_time = Integer.parseInt(input.nextToken());

        int[] time = new int[study_time + 1];

        for (int x = 0; x < chapter_num; x++) {

            int chapter_study_time, score;
            StringTokenizer chapter_input = new StringTokenizer(br.readLine());

            chapter_study_time = Integer.parseInt(chapter_input.nextToken());
            score = Integer.parseInt(chapter_input.nextToken());

            for (int y = study_time; y >= chapter_study_time; y--) {

                time[y] = Math.max(time[y], time[y - chapter_study_time] + score);
            }
        }

        System.out.println(time[study_time]);
    }
}