[BOJ 24107] 本棚 (Bookshelf)

백준 문제 링크

🔍 문제 분석

분석

• 책장에 꽂혀있는 책 중 이미 오름차순으로 정렬되어있는 책은 꺼낸 후 새로운 위치에 꽂을 필요가 없다. 따라서, 칼로리를 소비하게 되는 경우는 오름차순으로 정렬되어있지 않은 책의 순서를 바꾸는 경우이다. 칼로리 소모를 최소로 하기 위해서는 칼로리를 소모하지 않게 되는 경우를 최대로 할 필요가 있다.
• 따라서, 이 문제는 LIS(가장 긴 증가하는 부분수열) 문제의 일종으로 생각할 수 있다. 통상적인 LIS문제에서는 수열의 길이만을 고려하지만, 본 문제는 무게의 합을 고려해야 한다는 것이 차이점이다.
• DP를 활용하는 LIS문제의 풀이는 O(N^2)의 시간복잡도를 요구하지만, 세그먼트 트리를 이용한다면 시간복잡도를 O(NlogN)으로 낮출 수 있다.

  풀이

• arr[i]: 책장에 꽂혀있는 i번째 책의 번호
• w[i]: 책장에 꽂혀있는 i번째 책의 무게
• cache[i]: 구간 [1, i]에 존재하는 증가하는 부분수열 중 가장 큰 무게의 합, 이는 세그먼트 트리로 빠르게 계산할 수 있다.
• i번째 원소에 대하여 cache[arr[i]]와 cache[arr[i] - 1] + w[i]를 비교해가면서 cache[arr[i]]를 업데이트 하는 방법으로 문제를 풀이할 수 있다.
• 책을 넣고 빼는 과정에서 2번의 칼로리 소모가 있으므로 2 * ((전체 무게의 합) - (증가하는 부분 수열 중 가장 큰 무게의 합))이 정답이다.

💻 코드 구현

#include <bits/stdc++.h>
#define fastio cin.tie(0)->ios::sync_with_stdio(0)

using namespace std;
using ll = long long;
using pi = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vvll = vector<vector<ll>>;
using vll = vector<ll>;
using vpi = vector<pi>;

constexpr int MAX = 1e5;

int n, w[MAX], arr[MAX];
ll tree[4 * MAX];

int l(int node) {
    return 2 * node;
}

int r(int node) {
    return 2 * node + 1;
}

ll query(int begin, int end, int node, int left, int right) {
    if (left <= begin && end <= right) return tree[node];
    else if (left > end || begin > right) return 0;
    int mid = (begin + end) / 2;
    return max(query(begin, mid, l(node), left, right), query(mid + 1, end, r(node), left, right));
}

void update(int begin, int end, int node, int index, ll val) {
    if (index > end || begin > index) return;
    tree[node] = max(tree[node], val);
    if (begin == end) return;
    int mid = (begin + end) / 2;
    update(begin, mid, l(node), index, val);
    update(mid + 1, end, r(node), index, val);
}

int main() {
    fastio;

    cin >> n;
    for (int i = 0; i < n; ++i) cin >> w[i];
    for (int i = 0; i < n; ++i) cin >> arr[i];

    for (int i = 0; i < n; ++i) {
        ll max_sum = query(1, n, 1, 0, arr[i] - 1);
        ll cur_sum = query(1, n, 1, arr[i], arr[i]);
        if (cur_sum < max_sum + w[i]) {
            update(1, n, 1, arr[i], max_sum + w[arr[i] - 1]);
        }
    }

    ll sum = 0, max_sum = 0;
    for (int i = 0; i < n; ++i) {
        sum += w[i];
        max_sum = max(max_sum, query(1, n, 1, i + 1, i + 1));
    }
    cout << 2 * (sum - max_sum);
}

📝 코드 설명

🔧 트러블 슈팅

• arr[i]의 범위는 [1, N]이므로, 세그먼트 트리를 업데이트 할 때 구간에 주의한다.
• 코드에서 w[i]가 i번째 꽂혀있는 책에 대한 무게가 아닌, i번 책의 무게이므로 주의한다.

📚 참고자료

• IOI 2011 タイ大会 日本代表選手選考会 課題