백준 14728 (벼락치기) - java

https://www.acmicpc.net/problem/14728

14728번: 벼락치기

 

문제

ChAOS(Chung-ang Algorithm Organization and Study) 회장이 되어 일이 많아진 준석이는 시험기간에도 일 때문에 공부를 하지 못하다가 시험 전 날이 되어버리고 말았다. 다행히도 친절하신 교수님께서 아래와 같은 힌트를 시험 전에 공지해 주셨다. 내용은 아래와 같다.

1. 여러 단원을 융합한 문제는 출제하지 않는다.
2. 한 단원에 한 문제를 출제한다. 단, 그 단원에 모든 내용을 알고 있어야 풀 수 있는 문제를 낼 것이다.

이런 두가지 힌트와 함께 각 단원 별 배점을 적어 놓으셨다. 어떤 단원의 문제를 맞추기 위해서는 그 단원의 예상 공부 시간만큼, 혹은 그보다 더 많이 공부하면 맞출 수 있다고 가정하자. 이때, ChAOS 회장 일로 인해 힘든 준석이를 위하여 남은 시간 동안 공부해서 얻을 수 있는 최대 점수를 구하는 프로그램을 만들어 주도록 하자.

 

유형 : DP + 배낭 문제

 

접근 방식

• 너무 정석적인 형태의 배낭 문제이다.
• 시간 배열을 설정하고 각 문제 마다의 시간에 대해 최댓값을 구하면 된다. : dp[m+1]
• 각 문제에 대하여
  • 역순(m -> 0) 으로 시간 반복문을 돌면서
    • Math(dp[m-curT] + curP , dp[m]) 계산

전체 코드

import java.util.*;
import java.io.*;
public class Main {
    static int n = 0;
    static int m = 0;

    static int[] dp;

    static int[][] bag;

    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb =new StringBuilder();
        StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        dp = new int[m+1];
        bag = new int[n][2];

        for(int i=0;i<n;i++){
            st = new StringTokenizer(bf.readLine(), " ");

            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            bag[i][0] = x;
            bag[i][1] = y;
        }

        int max = 0;

        for(int i=0;i<n;i++){
            int curT = bag[i][0];
            int curP = bag[i][1];

            for(int j = m; j >=0 ; j--){
                if(j >= curT) {
                    dp[j] = Math.max(dp[j], dp[j - curT] + curP);
                }

                max = Math.max(max,dp[j]);
            }

        }

        System.out.println(max);
        bf.close();
    }

}