백준 17845 (수강 과목) - java

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

17845번: 수강 과목

 

문제

유니스트 컴퓨터공학과에 다니는 서윤이는 이번에 어떤 과목을 들을지 고민중이다. 학점을 잘 받을 수 있으면서도 중요한 과목을 듣고 싶은 서윤이는 모든 과목의 중요도와, 일정 이상의 학점을 받기 위해 필요한 공부시간을 다 적었다.

처음에는 모든 과목을 들으려고 했던 서윤이는 자신의 공부 시간에 한계가 있다는 것을 깨달았다. 그래서, 공부 시간의 한계를 초과하지 않으면서 과목의 중요도 합이 최대가 되도록 몇 개만 선택하여 수강하기로 마음먹었다.

중요도가 최대가 되도록 과목을 선택했을 때, 최대가 되는 중요도를 출력하는 프로그램을 작성하시오.

 

유형 : DP + 배낭 문제

 

접근 방식

• dp[i] : i 번 째 시간을 쏫아부었을 때 얻을 수 있는 최대의 중요도
• 정석적인 배낭 문제이다. 시간을 T , 중요도를 P라고 했을 때 다음과 같은 점화식을 세울 수 있다.
  • dp[i] = Max(dp[i] , dp[i-T] + P)
  • 1차원 dp 배열을 사용할거면 역순 탐색 (MaxTime -> CurT)인거 까먹지 말기 !

전체 코드

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

    static int[][] bag;

    static int[] dp;

    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());

        bag = new int[m][2];

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

            bag[i][0] = Integer.parseInt(st.nextToken());
            bag[i][1] = Integer.parseInt(st.nextToken());
        }

        dp = new int[n+1];
        int result = 0;

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

            if(curT > n)
                continue;

            for(int j=n;j>=curT;j--){

                dp[j] = Math.max(dp[j],dp[j-curT] + curP);

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

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