[Baekjoon] 수강 과목

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

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

public class Main{
    public static class Subject{
        private int importance;
        private int time;

        public Subject(int importance, int time){
            this.importance = importance;
            this.time = time;
        }
    }
    public static int answer;
    public static int N,K;
    public static Subject[] arr;
    public static int[][] dp;

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

        sol();

        print();
    }

    public static void sol() throws IOException{
        for(int i=1; i<=K; i++){
            for(int j=0; j<=N; j++){
                if (j>=arr[i].time) {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-arr[i].time] + arr[i].importance);
                    continue;
                }

                dp[i][j] = dp[i-1][j];
            }
        }
        answer = dp[K][N];
    }

    public static void init() throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st;

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

        N = Integer.parseInt(st.nextToken());//최대 시간
        K = Integer.parseInt(st.nextToken());//과목 수

        dp = new int[K+1][N+1];
        arr = new Subject[K+1];

        for(int i=1;i<=K; i++){
            st = new StringTokenizer(br.readLine());

            int I = Integer.parseInt(st.nextToken());//중요도
            int T = Integer.parseInt(st.nextToken());//시간

            arr[i] = new Subject(I, T);
        }
    }

    public static void print() throws IOException{
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        bw.write(String.valueOf(answer));
        bw.close();
    }
}

주요 개념

• DP

• 배낭 문제

접근 방법

• 1개만 고르는 경우에서 3번째 인덱스까지 탐색했을 때의 최대 중요도

  vs

• 1개만 고르는 경우에서 현재 과목의 시간값을 추가할 수 있을 만큼의 인덱스 값에 위치한 중요도 + 현재 과목의 중요도

• 점화식을 한글로 장황하게 풀면 이러하다