백준 14728[자바] java 벼락치기

문제 링크: https://www.acmicpc.net/problem/14728

14728번: 벼락치기

▶문제

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

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

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

---

▶입력

첫째 줄에는 이번 시험의 단원 개수 N(1 ≤ N ≤ 100)과 시험까지 공부 할 수 있는 총 시간 T(1 ≤ T ≤ 10000)가 공백을 사이에 두고 주어진다.

둘째 줄부터 N 줄에 걸쳐서 각 단원 별 예상 공부 시간 K(1 ≤ K ≤ 1000)와 그 단원 문제의 배점 S(1 ≤ S ≤ 1000)가 공백을 사이에 두고 주어진다.

---

▶출력

첫째 줄에 준석이가 얻을 수 있는 최대 점수를 출력한다.

▶해설

DP 문제 입니다.

 

조건을 살펴보겠습니다.

1. 가장 높은 점수를 얻도록 한다.

2. 총시간 안에 공부할 수 있어야 한다.

 

구하는 순서는 아래와 같습니다.

1. 현재 단원을 학습하는 데 걸리는 시간이 T보다 작다면 선택

if(map[i-1][0]<=t){
    dp[i][map[i-1][0]] = map[i-1][1];
}

2. 시간에 대해서 이전에 학습한 단원까지의 점수 VS 현재 단원을 공부한 점수 중 큰 것을 넣어준다.

for(int j=0; j<=t; j++){
    dp[i][j] = Math.max(dp[i][j],dp[i-1][j]);
}

3. 현재 단원을 공부를 하려고 할 경우 그때까지 학습한 점수가 있을 때 현재 공부하려고 하는 단원에 걸리는 시간 + 이전까지 사용한 시간이 T보다 낮은지 확인

if(dp[i-1][j]!=0){
	if(j+map[i-1][0]<=t){
    
    }
}

4. 지금까지 투자한 시간의 점수 VS 이전에 투자한 시간 + 현재의 시간을 더한 점수중 큰 것을 선택

if(j+map[i-1][0]<=t){
    dp[i][j+map[i-1][0]] = Math.max(dp[i-1][j]+map[i-1][1],dp[i][j+map[i-1][0]]);
}

이렇게 n번째까지 진행한 후 답을 구해줍니다.

int result=0;
for(int i=1; i<=t; i++){
    result = Math.max(result,dp[n][i]);
}

 

전체 코드

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

public class Main {
    static int n,t;
    static int[][]map;
    static int [][]dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        n = Integer.parseInt(s[0]);
        t= Integer.parseInt(s[1]);

        map = new int[n][2];

        for(int i=0; i<n; i++){
            String[] s1 = br.readLine().split(" ");
            map[i][0] = Integer.parseInt(s1[0]);
            map[i][1] = Integer.parseInt(s1[1]);
        }

        dp = new int[n+1][t+1];


        for(int i=1; i<=n; i++){
            if(map[i-1][0]<=t){
                dp[i][map[i-1][0]] = map[i-1][1];
            }

            for(int j=0; j<=t; j++){
                dp[i][j] = Math.max(dp[i][j],dp[i-1][j]);
            }
            for(int j=0; j<=t; j++){
                if(dp[i-1][j]!=0){
                    if(j+map[i-1][0]<=t){
                        dp[i][j+map[i-1][0]] = Math.max(dp[i-1][j]+map[i-1][1],dp[i][j+map[i-1][0]]);
                    }
                }
            }
        }

        int result=0;
        for(int i=1; i<=t; i++){
            result = Math.max(result,dp[n][i]);
        }
        System.out.println(result);
    }
}