[백준] 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 R_B - P_B R_A > 0 \quad\Longleftrightarrow P_A R_B > P_B R_A \quad\Longleftrightarrow \frac{P_A}{R_A} > \frac{P_B}{R_B}\]

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

---

2. 코드

1. Bottom-Up 2차원 dp [Java]

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[] M = br.readLine().split(" ");
        String[] P = br.readLine().split(" ");
        String[] R = br.readLine().split(" ");

        Item[] items = new Item[N];
        for (int i = 0; i < N; i++) {
            items[i] = new Item(Integer.parseInt(M[i]), Long.parseLong(P[i]), Integer.parseInt(R[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);
    }
}

2. Bottom-Up 1차원 dp [Java]

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[] M = br.readLine().split(" ");
        String[] P = br.readLine().split(" ");
        String[] R = br.readLine().split(" ");

        Item[] items = new Item[N];
        for (int i = 0; i < N; i++) {
            items[i] = new Item(Integer.parseInt(M[i]), Long.parseLong(P[i]), Integer.parseInt(R[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);
    }
}

3. Bottom-Up 2차원 dp [C++]

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

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

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

    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(), [](const Item& a, const Item& b) {
        return a.r * b.p < a.p * b.r;
    });

    vector<vector<long long>> dp(1 + n, vector<long long>(1 + t));
    for (int i = 1; i <= n; i++) {
        Item item = items[i - 1];
        int m = item.m;
        long 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] = max(dp[i - 1][j - r] + (m - j * p), dp[i - 1][j]);
            }
        }
    }

    cout << *max_element(dp[n].begin() + 1, dp[n].end());
}

4. Bottom-Up 1차원 dp [C++]

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

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

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

    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(), [](const Item& a, const Item& b) {
        return a.r * b.p < a.p * b.r;
    });

    vector<long long> dp(1 + t);
    for (Item item : items) {
        int m = item.m;
        long long p = item.p;
        int r = item.r;

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

    cout << *max_element(dp.begin() + 1, dp.end());
}

---

3. 풀이 정보

1. Bottom-Up 2차원 dp [Java]

언어	시간	메모리	코드 길이
Java 11	216 ms	58120 KB	1671 B

2. Bottom-Up 1차원 dp [Java]

언어	시간	메모리	코드 길이
Java 11	188 ms	19252 KB	1478 B

3. Bottom-Up 2차원 dp [C++]

언어	시간	메모리	코드 길이
C++ 17	32 ms	42792 KB	1063 B

4. Bottom-Up 1차원 dp [C++]

언어	시간	메모리	코드 길이
C++ 17	4 ms	2808 KB	862 B

---