BOJ 21761 - 초직사각형 링크
(2024.04.15 기준 P5)

문제

변수 $A$, $B$, $C$, $D$가 초기 값이 각각 $A_0$, $B_0$, $C_0$, $D_0$으로 주어진다. 그리고 $N$개의 카드가 주어진다. $i$번째 카드에는 문자 $T_i$와 자연수 $U_i$가 적혀있다. $T_i$는 A, B, C, D 중 하나이며, $i$번째 카드를 사용하면 $T_i$에 해당하는 변수의 값이 $U_i$ 증가한다.

정확히 $K$장을 사용해서 $A \times B \times C \times D$를 최대화할 때, 사용한 카드 $K$장 출력

알고리즘

각 카드 더미에서 한 장씩 고를 땐 그리디, 정렬. 고른 카드 중 선택하는 방법은 수학을 이용해서 계산을 최소화하기.

풀이

$K$장을 사용한다는 것은 $N$장을 사용한 상태에서 $N-K$장을 제외한다는 것과 동치이다. 후자로 살펴보자.

일단 $T_i$별로 카드를 나누고 합을 구하자. 물론 초기 값도 더하자. 이를 각각 $a$, $b$, $c$, $d$라고 하자.

$A$ 카드 더미에서 임의의 카드를 선택해서 제외한다고 생각해보자. 그 카드에 적혀있는 자연수가 $n$이라면, $a \times b \times c \times d$의 감소량은 $n \times b \times c \times d$가 된다. 그럼 당연히 각 카드 더미에서는 적혀있는 자연수가 제일 작은 카드부터 제외할지 고려하면 됨을 알 수 있다.

하지만 위와 같은 그리디 접근법은 모든 카드 더미를 통틀어서 적용하면 안된다.
만약 $A$ 카드 더미에 $5$, $7$이 적혀있는 카드 $2$장이 있고, $B$ 카드 더미에 $2$가 적혀있는 카드 $1$장이 있다고 생각해보자.
모든 카드 더미를 통틀어서 가장 값이 작은 카드는 $2$가 적혀있는 $B$ 카드지만, 이를 제외하면 $a \times b \times c \times d = 12$가 된다. 하지만 $5$가 적혀있는 $A$ 카드를 제외하면 $a \times b \times c \times d = 14$가 된다. 그래서 일일이 비교해볼 수 밖에 없게 된다.

각 카드 더미에서 가장 값이 작은 카드를 제외한다면 $a \times b \times c \times d$는 각각 $(a - A_{min}) \times b \times c \times d$, $a \times (b - B_{min}) \times c \times d$, $a \times b \times (c - C_{min}) \times d$, $a \times b \times c \times (d - D_{min})$가 된다. 이들을 각각 구해서 가장 높은 값이 나오는 카드를 제외하면 되지만, 각 변수의 합은 최대 $200\,000\,000\,000$이다. 평균적으로 $50\,000\,000\,000$인데, 이와 같은 값을 네 번 곱하는 방식을 네 번 비교하면, TLE가 날 뿐더러 오버플로우 문제도 생긴다. 어떻게 해야할까?

$A$와 $B$만 비교해보자. $(a - A_{min}) \times b \times c \times d < a \times (b - B_{min}) \times c \times d$와 같은 부등식이 성립하는지 확인하게 된다. 그런데 이 부등식을 정리를 하면?
$(a - A_{min}) \times b \times c \times d < a \times (b - B_{min}) \times c \times d$
$(a - A_{min}) \times b < a \times (b - B_{min})$
$a \times b - b \times A_{min}< a \times b - a \times B_{min}$
$a \times B_{min} < b \times A_{min}$
이렇게 정리가 된다. 물론 성립하면 $B$인 카드를 선택, 아니면 $$인 카드를 선택해서 제외하면 된다.

위와 같은 비교를 $A$와 $B$로 한 번, 선택된 카드와 $C$로 한 번, 선택된 카드와 $D$로 한 번하면 된다.
이렇게 선택된 카드를 제외하고 $a$, $b$, $c$, $d$ 중 하나를 조정하면 된다.

코드

• C++

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

typedef long long ll;

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

    int N, K; cin >> N >> K;
    ll a, b, c, d; cin >> a >> b >> c >> d;

    // Ti별로 카드를 분류한다.
    // N개의 카드를 모두 사용하고, N-K개의 카드를 빼는 방식을 택한다.
    vector<ll> A, B, C, D;
    char T; ll U;
    for (int i = 0; i < N; i++){
        cin >> T >> U;
        if (T == 'A'){
            a += U;
            A.push_back(U);
        }
        else if (T == 'B'){
            b += U;
            B.push_back(U);
        }
        else if (T == 'C'){
            c += U;
            C.push_back(U);
        }
        else{
            d += U;
            D.push_back(U);
        }
    }

    // 변수의 감소량이 적을수록 부피가 최대화된다.
    // 그러므로 내림차순으로 정렬하고
    // back으로 비교한다.
    sort(A.begin(), A.end(), greater<ll>());
    sort(B.begin(), B.end(), greater<ll>());
    sort(C.begin(), C.end(), greater<ll>());
    sort(D.begin(), D.end(), greater<ll>());

    N -= K;
    vector<char> compare;
    while (N--){

        /* 각 카드 더미마다 비교할 것이다.
        만약 각 Ti별로 제일 작은 값을 뺀다면
        부피는 각각 (a - Amin)bcd, a(b - Bmin)cd, ab(c - Cmin)d, abc(d - Dmin)이다.
        이중에서 부피가 가장 큰 것을 선택해야 한다.
        Ti가 A, B인 카드를 비교하면 (a - Amin)bcd < a(b - Bmin)cd 식이 나오는데 이를 정리하면
        aBmin < bAmin이 된다.
        이를 A, B로 비교하고, 선택된 Ti와 C를 비교하고, 선택된 Ti와 D를 비교하면 된다. */

        // 각 카드 더미마다 카드가 있는지 확인
        compare.clear();
        if (!A.empty()) compare.push_back('A');
        if (!B.empty()) compare.push_back('B');
        if (!C.empty()) compare.push_back('C');
        if (!D.empty()) compare.push_back('D');

        // 1개가 선택될 때까지 반복
        while (compare.size() > 1){
            char s = compare.back(); compare.pop_back();
            char t = compare.back(); compare.pop_back();
            if (s == 'D'){
                if (t == 'A'){
                    if (D.back() * a <= A.back() * d) compare.push_back(s);
                    else compare.push_back(t);
                }
                else if (t == 'B'){
                    if (D.back() * b <= B.back() * d) compare.push_back(s);
                    else compare.push_back(t);
                }
                else{
                    if (D.back() * c <= C.back() * d) compare.push_back(s);
                    else compare.push_back(t);
                }
            }
            else if (s == 'C'){
                if (t == 'A'){
                    if (C.back() * a <= A.back() * c) compare.push_back(s);
                    else compare.push_back(t);
                }
                else{
                    if (C.back() * b <= B.back() * c) compare.push_back(s);
                    else compare.push_back(t);
                }
            }
            else{
                if (B.back() * a <= A.back() * b) compare.push_back(s);
                else compare.push_back(t);
            }
        }

        // 선택된 카드를 뺀다.
        if (compare[0] == 'A') a -= A.back(), A.pop_back();
        else if (compare[0] == 'B') b -= B.back(), B.pop_back();
        else if (compare[0] == 'C') c -= C.back(), C.pop_back();
        else d -= D.back(), D.pop_back();
    }

    for (ll a: A) cout << "A " << a << '\n';
    for (ll b: B) cout << "B " << b << '\n';
    for (ll c: C) cout << "C " << c << '\n';
    for (ll d: D) cout << "D " << d << '\n';
}

• Python

import sys; input = sys.stdin.readline

N, K = map(int, input().split())
a, b, c, d = map(int, input().split())

# Ti별로 카드를 분류한다.
# N개의 카드를 모두 사용하고, N-K개의 카드를 빼는 방식을 택한다.
A = []; B = []; C = []; D = []
for _ in range(N):
    T, U = input().split(); U = int(U)
    if T == 'A':
        a += U
        A.append(U)
    elif T == 'B':
        b += U
        B.append(U)
    elif T == 'C':
        c += U
        C.append(U)
    else:
        d += U
        D.append(U)

# 변수의 감소량이 적을수록 부피가 최대화된다.
# 그러므로 내림차순으로 정렬하고
# back으로 비교한다.
A.sort(reverse = True)
B.sort(reverse = True)
C.sort(reverse = True)
D.sort(reverse = True)

for _ in range(N - K):

    ''' 각 카드 더미마다 비교할 것이다.
    만약 각 Ti별로 제일 작은 값을 뺀다면
    부피는 각각 (a - Amin)bcd, a(b - Bmin)cd, ab(c - Cmin)d, abc(d - Dmin)이다.
    이중에서 부피가 가장 큰 것을 선택해야 한다.
    Ti가 A, B인 카드를 비교하면 (a - Amin)bcd < a(b - Bmin)cd 식이 나오는데 이를 정리하면
    aBmin < bAmin이 된다.
    이를 A, B로 비교하고, 선택된 Ti와 C를 비교하고, 선택된 Ti와 D를 비교하면 된다. '''

    # 각 카드 더미마다 카드가 있는지 확인
    compare = []
    if A:
        compare.append('A')
    if B:
        compare.append('B')
    if C:
        compare.append('C')
    if D:
        compare.append('D')

    # 1개가 선택될 때까지 반복
    while len(compare) > 1:
        s = compare.pop()
        t = compare.pop()
        if s == 'D':
            if t == 'A':
                if D[-1] * a <= A[-1] * d:
                    compare.append(s)
                else:
                    compare.append(t)
            elif t == 'B':
                if D[-1] * b <= B[-1] * d:
                    compare.append(s)
                else:
                    compare.append(t)
            else:
                if D[-1] * c <= C[-1] * d:
                    compare.append(s)
                else:
                    compare.append(t)
        elif s == 'C':
            if t == 'A':
                if C[-1] * a <= A[-1] * c:
                    compare.append(s)
                else:
                    compare.append(t)
            else:
                if C[-1] * b <= B[-1] * c:
                    compare.append(s)
                else:
                    compare.append(t)
        else:
            if B[-1] * a <= A[-1] * b:
                compare.append(s)
            else:
                compare.append(t)

    # 선택된 카드를 뺀다.
    if compare[0] == 'A':
        a -= A.pop()
    elif compare[0] == 'B':
        b -= B.pop()
    elif compare[0] == 'C':
        c -= C.pop()
    else:
        d -= D.pop()

for a in A:
    print('A', a)
for b in B:
    print('B', b)
for c in C:
    print('C', c)
for d in D:
    print('D', d)