[BOJ/백준] 24395 - 명진이의 신년계획

24395번: 명진이의 신년계획

---

DP + 배낭

---

---

• 제목

명진이의 신년계획

---

• 조건

시간 제한 : 1 초

메모리 제한 : 512 MB 

---

• 문제

카오스 동아리 사람들은 모두 코딩에 미쳐있기 때문에 주기적으로 약을 처방받는다. 동아리의 회장 명진이는 새해를 맞아 이들 모두를 치료하고자 한다.

그들이 걸린 질병은 총 M종류이며 각 질병은 0 이상, 100 이하의 위험도를 지닌다. 회원들은 걸린 질병에 따라 특정 개수의 빨강, 파랑 알약을 처방받는다.

처방받는 알약의 수와 위험도가 모두 같은 서로 다른 질병이 존재할 수 있다.
하나의 질병에 대해 여러 번 처방받을 수 없다.
처방받는 알약의 수는 종류별 50개 이하이며 2종류를 합해 최소 1개 이상이다.
명진이는 신년계획에 따라 학생들의 위험군을 계산해 치료 순서 리스트를 작성하고자 한다.

위험군은 해당 학생이 지닐 수 있는 질병들의 위험도 합계의 최대치로 정해진다.
리스트는 저위험군 학생부터 나열되며, 위험군이 같을 경우 번호가 앞선 학생이 먼저 나온다.
만약 학생이 지닌 알약이 어떠한 처방으로도 만들 수 없는 경우, 해당 학생은 미친 척하는 정상인으로 위험군이 0이다.
N명의 학생이 처방받은 빨강, 파랑 알약의 수가 주어졌을 때, 명진이를 도와 치료 순서 리스트를 작성해보자.

---

• 입력

첫째 줄에 N (1 ≤ N ≤ 100,000), M (1 ≤ M ≤ 100)이 공백을 두고 주어진다.

둘째 줄부터 M개의 줄에 걸쳐 M개의 질병에 처방할 빨강, 파랑 알약의 수 Ri , Bi (0 ≤ Ri , Bi ≤ 50, Ri + Bi ≥ 1)와 위험도 Di (0 ≤ Di ≤ 100)가 공백을 두고 주어진다.

M+2번째 줄부터 N 개의 줄에 걸쳐 N 명의 학생이 처방받은 빨강, 파랑 알약의 수 R'i , B'i (0 ≤ R'i , B'i ≤ 50, R'i + B'i  ≥ 1)가 공백을 두고 주어진다.

---

• 출력

N개의 줄에 걸쳐 학생 번호와 위험군을 빈칸을 두고 리스트 순서대로 출력한다.

---

예제 입력1	예제 출력1
2 3 1 1 2 2 2 4 3 3 5 3 3 5 5	1 6 2 9

---

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer st;

    static class STUDENT implements Comparable<STUDENT> {
        int INDEX;
        int DANGER;

        public STUDENT(int INDEX, int DANGER) {
            this.INDEX = INDEX;
            this.DANGER = DANGER;
        }

        @Override
        public int compareTo(STUDENT o) {
            if (this.DANGER == o.DANGER) {
                return Integer.compare(this.INDEX, o.INDEX);
            }
            return Integer.compare(this.DANGER, o.DANGER);
        }
    }

    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[][] dp = new int[50 + 1][50 + 1];
        for(int i = 0; i <= 50; i++){
            for(int j = 0; j <= 50; j++){
                dp[i][j] = -1;
            }
        }
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int RED = Integer.parseInt(st.nextToken());
            int BLUE = Integer.parseInt(st.nextToken());
            int DANGER = Integer.parseInt(st.nextToken());
            for (int n = 50; n >= 0; n--) {
                for (int m = 50; m >= 0; m--) {
                    if (RED > n || BLUE > m) continue;
                    if (dp[n - RED][m - BLUE] == -1) continue;

                    dp[n][m] = Math.max(dp[n][m], dp[n - RED][m - BLUE] + DANGER);
                }
            }
            dp[RED][BLUE] = Math.max(dp[RED][BLUE], DANGER);
        }

        STUDENT[] answer = new STUDENT[N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int RED = Integer.parseInt(st.nextToken());
            int BLUE = Integer.parseInt(st.nextToken());
            answer[i] = new STUDENT(i + 1, Math.max(dp[RED][BLUE], 0));
        }
        Arrays.sort(answer);
        for (int i = 0; i < N; i++) {
            sb.append(answer[i].INDEX).append(" ").append(answer[i].DANGER).append('\n');
        }
        System.out.print(sb);
    }
}