[BOJ] 17524 Dryer

문제 링크 : www.acmicpc.net/problem/17524

문제 풀이

가장 먼저 해야 하는 관찰은 다음과 같다.

• $t_i$가 같은 옷이 2개 있다면 어차피 $w_i$가 큰 쪽이 더 오래 걸릴 것이기 때문에, 같이 넣고 말려도 무방하다. 따라서 의미 있는 옷은 각 $t_i$에 대해서 유일하므로, $1\le N\le61$과 사실상 같다.

그 다음으로 해야 하는 관찰들은 다음과 같다.

• 어떤 옷들의 집합을 같은 건조기에 넣고 돌린다면, 그 건조기의 온도는 반드시 옷 중 $t_i$의 최솟값과 같아야 한다. 이는 매우 자명하다.
• 어떤 건조기가 이미 $x$초 동안 돌아간다면, $x$초 이하를 소모하는 다른 옷을 끼워 넣어도 상관없다.

$k=3$일때만 해결하면 그 아래는 쉽게 해결할 수 있으므로 이 경우에 대해서만 따지자. 일반성을 잃지 않고 각 건조기의 온도를 $l_1 > l_2 > l_3$라고 하면, 두 번째 관찰로 인해 $l_3$이 모든 옷 중 온도의 최솟값과 같게 설정될 것이라는 것을 알 수 있다. 3번 건조기에 옷을 얼마나 넣을지를 생각해보자. 모든 옷들을 $l_3$에서 걸리는 시간의 오름차순으로 정렬한다고 생각해 보면, 세 번째 관찰로 인해 $l_3$에는 정렬된 배열의 prefix에 해당하는 옷들이 들어감을 알 수 있다. 따라서 $l_3$에 옷을 넣는 경우의 수는 총 $N$가지이다.

모든 경우에 대해서 어떤 옷 집합들을 건조기에 넣었으므로, $k=2$인 문제를 해결한다고 생각할 수 있다. 이는 위에서 설명한 방법과 완전히 동일한 방식으로 $k=1$인 문제로 축소할 수 있다. $k=1$일때는 선형에 풀리므로, 총 시간복잡도 $O(N^3 \lg ^2 N)$에 해결할 수 있다. 여기서 $N$은 문제에서 주어진 $N$이 아닌 축소된 $N=61$이다.

소스 코드

#include <bits/stdc++.h>
#include <random>
#include <cassert>
#define all(x) (x).begin(), (x).end()
#define endl "\n"
#define ends " "
#define pb(x) push_back(x)
#define fio() ios_base::sync_with_stdio(0); cin.tie(0)
#define fileio() ifstream file_in("input.txt");ofstream file_out("output.txt")
#define double long double
/*#define cin file_in
#define cout file_out*/

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tpi;
typedef tuple<ll, ll, ll> tpl;
typedef pair<double, ll> pdl;

const int MOD = 1000000007;
const ll LMOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const double pi = acos(-1);
const double eps = 1e-10;
const int dx[] = { 0,1,0,-1 };
const int dy[] = { 1,0,-1,0 };

int n, k;
int w[101];

int bt(vector<pii> v, int k) {
    if (v.empty()) return 0;

    int t = min_element(all(v))->first;
    sort(all(v), [&](pii a, pii b) {
        return (a.first - t) * a.second >= (b.first - t) * b.second;
        });
    if (k == 1) return (v[0].first - t) * v[0].second + 30;

    int mi = (v[0].first - t) * v[0].second + 30, m = v.size();
    for (int i = 0; i < m - 1; i++) {
        auto r = v.back();
        int val = (r.first - t) * r.second + 30;
        v.pop_back();
        mi = min(mi, bt(v, k - 1) + val);
    }
    return mi;
}

int main() {
    fio();
    cin >> n >> k;

    int mi = 101;
    memset(w, -1, sizeof(w));
    for (int i = 0; i < n; i++) {
        int t1, t2; cin >> t1 >> t2;
        w[t1] = max(w[t1], t2);
    }
    vector<pii> v;
    for (int i = 40; i <= 100; i++) if (w[i] != -1) v.emplace_back(i, w[i]);
    cout << bt(v, k);

    return 0;
}

이 코드는 로그를 하나 더 붙여서 구현하였다.