[백준] 17845 수강 과목 - Java

 

 

 

문제 출저

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

17845번: 수강 과목

 

 

 

문제 풀이

배낭 문제, 냅색 문제와 같이 풀었습니다. 

2차원 DP를 만들어 기존의 값과 새로운 값이 추가했을 때를 비교하여 더 큰 값을 메모리에 저장하는 형식으로 문제를 풀었습니다. 

 

 

 

소스코드

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

public class Main {

    static int n;
    static int k;

    static int[] ts;
    static int[] is;
    static int[][] dp;


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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        ts = new int[k];
        is = new int[k];

        for (int i = 0; i < k; i++) {
            st = new StringTokenizer(br.readLine());
            is[i] = Integer.parseInt(st.nextToken());
            ts[i] = Integer.parseInt(st.nextToken());
        }

        dp = new int[k+1][n+1];
        for (int i = 1; i < k+1; i++) {

            int time = ts[i-1];
            int important = is[i-1];

            for (int j = 1; j < n+1; j++) {
                dp[i][j] = dp[i-1][j];
                if(j - time >= 0)dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j - time] + important);
            }
        }

//        for (int i = 0; i < k+1; i++) {
//            System.out.println(Arrays.toString(dp[i]));
//        }

        System.out.println(dp[k][n]);








    }

}