LUNCHBOX (중, p. 376)

문제#

어떻게 풀었나?#

영어 능력 부족으로 처음엔 잘못 해석해서 여러번 WA를 받았다.

각 도시락마다 $(m_i, e_i)$가 있고, 어떤 도시락을 먹는 동안에는 다음 도시락의 전자레인지 시간만 일부 겹쳐서 처리할 수 있다고 생각했다. 하지만 다시 읽어보니, 한 도시락을 먹는 동안에는 이후에 전자레인지에 넣는 모든 도시락의 가열 시간이 전부 겹칠 수 있다는 것이 핵심이었다.

이 점을 이해하고 나면 문제의 구조가 조금 더 명확해진다.

그럼에도 불구하고 이 문제는 체감 난이도가 꽤 높았다. 책에서는 난이도를 ‘하’로 분류했지만, 개인적으로는 ‘중’ 정도는 된다고 느꼈다. 풀이 자체는 떠올리기 어렵지 않지만, 왜 그 풀이가 항상 최적인지를 납득하는 과정이 쉽지 않기 때문이다.

핵심 아이디어#

이 문제는 먹는 시간이 긴 도시락부터 전자레인지에 돌리면 최소 점심 시간이 된다.

하지만 이 선택이 항상 최적이라는 사실은, MATCHORDER 같은 문제처럼 즉각적으로 “당연하다”라고 느껴지지는 않는다. 그래서 이 문제는 증명이 필요하다. 증명 방법은 책에서 소개하는 2가지 증명법,

탐욕적 선택 속성 증명
최적 부분 구조 증명

을 적용해보면 된다.

1. 탐욕적 선택 속성 증명#

모든 도시락 중에서 먹는 시간이 가장 긴 도시락을 $i$라고 하자.

그리고 $i$가 아닌 도시락 중, 어떤 도시락 $j$를 맨 처음 전자레인지에 넣는 최적해가 존재한다고 가정한다.

이때, 맨 처음에 $j$ 대신 $i$를 넣어도 여전히 최적해가 성립함을 보이면 된다.

도시락을 순서대로 전자레인지에 넣을 때, 전체 점심 시간은 $\Sigma_{p=0}^km_p+e_k$ 형태로 결정된다.

이제 두 가지 경우를 생각해보자.

(1) 최대 시간을 만드는 도시락이 $i$가 아닌 경우#

이 경우, 전체 점심 시간은 어떤 도시락 $k$에 의해 $\Sigma_{p=0}^km_p+e_k$ 로 결정된다.

$i$와 $j$의 순서를 바꾸더라도 이 값에는 영향을 주지 않으므로, 해는 그대로 최적이다.

(2) 최대 시간을 만드는 도시락이 $i$인 경우#

이때의 점심 시간은 $\Sigma_{p=0}^im_p+e_i$ 이다.

만약 $i$ 대신 $j$를 같은 위치에 두면 점심 시간은 $\Sigma_{p=0}^im_p+e_j$ 가 되는데, $e_i≥e_j$이므로 이 값은 원래 시간보다 커질 수 없다.

즉, 처음에 $j$를 선택한 최적해는 항상 $i$를 선택한 해로 바꿀 수 있다.

따라서 먹는 시간이 가장 긴 도시락을 먼저 선택하는 것은 탐욕적으로도 안전한 선택이다.

2. 최적 부분 구조 증명#

가장 먼저 먹는 시간이 가장 긴 도시락 하나를 선택했다고 하자. 이후 남은 N−1개의 도시락을 보게 되는데, 이 문제는 원래 문제에서 도시락 하나만 제거된 것일 뿐 문제의 구조 자체는 변하지 않는다.

즉,

전체 문제에서 한 번의 탐욕적 선택을 하고 나면
남은 문제도 동일한 형태의 문제이며
다시 같은 기준(먹는 시간이 가장 긴 도시락 우선)으로 풀 수 있다.

따라서 이 문제는 최적 부분 구조를 만족한다.

정답 코드#

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n;
struct Info{
    int m,e,idx;
    Info(){}
    Info(int m, int e):m(m),e(e) {}
    bool operator<(const Info & rhs) const {
        if(e==rhs.e) return m<rhs.m;
        else return e>rhs.e;
    }
};
ll ans;
Info v[10001];
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int tc; cin >> tc;

    while(tc--) {
        cin >> n;
        for(int i=0; i<n; i++) {
            cin >> v[i].m;
        }
        for(int i=0; i<n; i++) {
            cin >> v[i].e;
        }

        sort(v,v+n);

        ll ans=0, sum=0;
        for(int i=0; i<n; i++) {
            sum += v[i].m;
            ans = max(ans, sum + v[i].e);
        }

        printf("%lld\n", ans);
    }
    return 0;
}