[BaekJoon] #13448 - SW 역량 테스트 [Java][C++]

문제 링크

---

1. 아이디어

$T$분 동안 $N$개의 문제 중 어떤 문제를 어떤 순서로 풀어야 점수가 최대가 될지 찾는 문제다. 각 문제가 주는 점수가 고정되어 있다면 0/1 배낭 문제를 활용해서 해결할 수 있는데 문제가 주는 점수가 유동적이라서 일반적인 방법으로는 안된다.

핵심은 배낭에 담되 어떤 순서로 담아야 최댓값이 되느냐인데 $\dfrac{P}{R}$가 큰 문제를 먼저 담으면 같은 문제들을 담았을 때 점수가 최대가 된다.

두 문제 $A$, $B$가 있다고 했을 때, 시각 $t$에 $A$를 먼저 풀고 $B$를 푼 경우 점수의 합은 아래와 같다.

\[S_{AB} = (M_A - (t + R_A) \times P_A) + (M_B - (t + R_A + R_B) \times P_B)\]

동일한 시각 $t$에 $B$를 먼저 풀고 $A$를 푼 경우 점수의 합은 아래와 같다.

\[S_{BA} = (M_B - (t + R_B) \times P_B) + (M_A - (t + R_B + R_A) \times P_A)\]

이때 $S_{AB} - S_{BA} > 0$이면 $A$를 $B$보다 먼저 푸는 것이 이득이다.

\[S_{AB} - S_{BA} = P_A \times R_B - P_B \times R_A > 0 \quad\Longleftrightarrow P_A \times R_B > P_B \times R_A \quad\Longleftrightarrow \frac{P_A}{R_A} > \frac{P_B}{R_B}\]

따라서 $\dfrac{P}{R}$가 큰 문제를 먼저 풀도록 정렬을 수행한 후 0/1 배낭 문제를 적용하면 된다.(같은 문제들을 골라도 정렬 후 배낭을 하면 점수가 최대가 된다.)

---

2. 복잡도

접근	시간	공간
배열 DP	$O(N \log N + N \times M)$	$O(N \times M)$
공간 최적화 DP	$O(N \log N + N \times M)$	$O(N + M)$

($N$ = 입력값 n, $M$ = 입력값 t)

---

3. 코드

풀이 1: 배열 DP [Java][C++]

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

public class Main {

    static class Item {
        int m;
        long p;  // 점수 계산에서 오버플로우 방지
        int r;

        public Item(int m, long p, int r) {
            this.m = m;
            this.p = p;
            this.r = r;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int t = Integer.parseInt(st.nextToken());

        String[] marr = br.readLine().split(" ");
        String[] parr = br.readLine().split(" ");
        String[] rarr = br.readLine().split(" ");

        Item[] items = new Item[n];
        for (int i = 0; i < n; i++) {
            items[i] = new Item(Integer.parseInt(marr[i]), Long.parseLong(parr[i]), Integer.parseInt(rarr[i]));
        }
        Arrays.sort(items, (o1, o2) -> Long.compare(o1.r * o2.p, o1.p * o2.r));

        long[][] dp = new long[1 + n][1 + t];
        for (int i = 1; i <= n; i++) {
            Item item = items[i - 1];
            int m = item.m;
            long p = item.p;
            int r = item.r;

            for (int j = 1; j <= t; j++) {
                if (j < r) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j - r] + (m - j * p), dp[i - 1][j]);
                }
            }
        }

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

        System.out.println(max);
    }
}

#include <bits/stdc++.h>
using namespace std;

long long dp[1 + 50][1 + 100000];

struct Item {
    int m;
    long long p;  // 점수 계산에서 오버플로우 방지
    int r;
};

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, t;
    cin >> n >> t;

    vector<Item> items(n);
    for (int i = 0; i < n; i++) cin >> items[i].m;
    for (int i = 0; i < n; i++) cin >> items[i].p;
    for (int i = 0; i < n; i++) cin >> items[i].r;
    sort(items.begin(), items.end(), [](auto& a, auto& b) {
        return a.r * b.p < a.p * b.r;
    });

    for (int i = 1; i <= n; i++) {
        auto [m, p, r] = items[i - 1];

        for (int j = 1; j <= t; j++) {
            if (j < r) {
                dp[i][j] = dp[i - 1][j];
            } else {
                dp[i][j] = max(dp[i - 1][j - r] + (m - j * p), dp[i - 1][j]);
            }
        }
    }

    long long mx = 0;
    for (int j = 1; j <= t; j++) {
        mx = max(mx, dp[n][j]);
    }

    cout << mx;
}

---

풀이 2: 공간 최적화 DP [Java][C++]

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

public class Main {

    static class Item {
        int m;
        long p;  // 점수 계산에서 오버플로우 방지
        int r;

        public Item(int m, long p, int r) {
            this.m = m;
            this.p = p;
            this.r = r;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int t = Integer.parseInt(st.nextToken());

        String[] marr = br.readLine().split(" ");
        String[] parr = br.readLine().split(" ");
        String[] rarr = br.readLine().split(" ");

        Item[] items = new Item[n];
        for (int i = 0; i < n; i++) {
            items[i] = new Item(Integer.parseInt(marr[i]), Long.parseLong(parr[i]), Integer.parseInt(rarr[i]));
        }
        Arrays.sort(items, (o1, o2) -> Long.compare(o1.r * o2.p, o1.p * o2.r));

        long[] dp = new long[1 + t];
        for (Item item : items) {
            int m = item.m;
            long p = item.p;
            int r = item.r;

            for (int j = t; j >= r; j--) {
                dp[j] = Math.max(dp[j - r] + (m - j * p), dp[j]);
            }
        }

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

        System.out.println(max);
    }
}

#include <bits/stdc++.h>
using namespace std;

long long dp[1 + 100000];

struct Item {
    int m;
    long long p;  // 점수 계산에서 오버플로우 방지
    int r;
};

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, t;
    cin >> n >> t;

    vector<Item> items(n);
    for (int i = 0; i < n; i++) cin >> items[i].m;
    for (int i = 0; i < n; i++) cin >> items[i].p;
    for (int i = 0; i < n; i++) cin >> items[i].r;
    sort(items.begin(), items.end(), [](auto& a, auto& b) {
        return a.r * b.p < a.p * b.r;
    });

    for (auto [m, p, r] : items) {
        for (int j = t; j >= r; j--) {
            dp[j] = max(dp[j - r] + (m - j * p), dp[j]);
        }
    }

    long long mx = 0;
    for (int j = 1; j <= t; j++) {
        mx = max(mx, dp[j]);
    }

    cout << mx;
}

---