나를 위한 기록

문제 링크: https://www.acmicpc.net/problem/7983

문제를 요약해봅시다.

• 과제 \(N\)개를 적절한 순서대로 배치하여 모든 과제를 늦지 않게 해결해야 합니다. 과제 \(i\)를 \(d_i, t_i\)라 할 때, 이 과제는 적어도 시간 \(t_i - d_i\)이 되기 전에 시작해야 합니다.
• 가장 먼저 시작하는 과제의 시작 시간을 최대화해야 합니다.
• 문제에는 자세히 적혀있지 않지만, 한 번에 동시에 최대 하나의 과제만 할 수 있습니다.

음.. 문제 설명을 읽으니 정말 공감이 마구 되네요.. ㅠ

우선 제일 간단하게 생각해봅시다. 모든 과제를 각각의 기한 \(t_i\) 내에 해결하려면 그냥 시간이 \(t_i - d_i\)일 때 과제 \(i\)를 시작하면 됩니다. 정말 간단하네요!

이 방법은 과제의 시작 시간과 제출 기한이 전혀 겹치지 않는다면 사용할 수 있습니다. 하지만 냉혹하게도 과제들은 여러 개가 연속으로 마구 나올 수 있고, 제출 기한도 겹칠 수 있습니다. 다른 방법을 생각해 봐야겠죠.

과제를 할 때 굉장히 중요한 것은 제출 기한입니다. 따라서 제출 기한에 초점을 두고 해보도록 합시다.

현재 이 문제는 모든 과제를 제출 기한에 늦지 않게 제출하되, 최대한 늦게 시작하는 날짜 구하기인데요, 이를 뒤집어 생각해 봅시다.

제출 기한을 과제를 받는 시간이라고 생각하는 겁니다! 시간의 흐름을 반대로 생각해서 제출 기한에 과제를 받고, 과제에 걸리는 시간만큼 지난 후 과제가 끝난다고 생각해봅시다.

이러면 이 문제를 모든 과제를 시작할 수 있을 때 바로 시작하고, 다 끝냈을 때 남는 시간 구하기로 바꿔 생각할 수 있습니다.

문제의 설명에서 '오늘 아무 것도 안 해도 과제를 마무리 할 수 있는 방법이 존재함이 보장된다.' 라 했으므로 답은 항상 존재합니다.

문제를 바꿔 생각하면 이렇게 해결할 수 있습니다.

• 과제를 제출 기한이 느린 순서대로 정렬합니다.
• 시간 \(t_i\)이 제출 기한인 과제는 시간 \(t_i\)에 시작해서, 시간 \(t_i - d_i\)에 끝난다고 생각할 수 있습니다.
• 다음 과제의 제출 기한을 \(t_j\)라 할 때, \(t_j < t_i-d_i\)이면 다음 과제는 \(t_j\)에 시작하고, \(t_j \ge t_i+d_i\)이면 \(t_i+d_i\)에 시작합니다.
• 이를 모든 과제에 대해 반복한 후, 마지막 과제가 끝나는 시간을 기록합니다.

시간복잡도는 과제 \(N\)개의 정렬과 과제 \(N\)개를 순회하며 시간을 계산하는 두 단계가 있으므로 \(O(N \log N + N) = O(N \log N)\) 입니다.

소스코드 (C++)

#include <bits/stdc++.h>

#define fastio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;
typedef long long ll;

// 과제 제출 기한의 역순으로 정렬하게 해주는 함수.
bool cmp_deadline(const pair<int, int> &p1, const pair<int, int> &p2) {
    return p1.second > p2.second;
}

int main() {
    fastio;
    
    int n;
    cin >> n;
    
    // {과제 하는데 걸리는 시간, 과제 제출 기한}
    vector<pair<int, int>> hw(n);
    
    for (int i = 0; i < n; i++) {
        int d, t;
        cin >> d >> t;
        
        hw[i] = make_pair(d, t);
    }
    
    sort(hw.begin(), hw.end(), cmp_deadline);
    
    int start_time = hw[0].second;
    
    for (int i = 0; i < n; i++) {
        start_time = min(start_time, hw[i].second);
        start_time -= hw[i].first;
    }
    
    cout << start_time;
    
    return 0;
}

문제 링크: https://www.acmicpc.net/problem/13164

문제를 요약하면 다음과 같습니다.

• 주어진 오름차순으로 정렬된 배열을 \(A\)라 할 때, \(A\)를 \(K\)개의 조로 분할해야 합니다. 이때 \(K\)개의 조의 조원들은 서로 인접해 있어야 합니다.
• \(K\)개의 조로 나눌 때 아무렇게나 나누면 안되고, 각 조들의 비용 총합이 최소가 되도록 분할해야 합니다. 조의 비용은 해당 조의 (최댓값 - 최솟값)으로 계산합니다.

\(A\)가 정렬되어 있고, 각 조의 조원들이 서로 인접해 있으므로 각 조의 비용은 조원이 \(i, i + 1, i + 2, ... , j - 1, j\)일때 \(A_j - A_i\)가 됩니다.

이제 \(K\)개 조로 분할하는 방법을 생각해 봅시다. \(N\)명의 학생들을 \(K\)개 조로 분할해서 비용 총합이 최소인 것을 찾으려면 어떻게 해야 할까요?

가장 생각하기 쉬운 방법은 \(K\)개 조로 나누는 모든 방법을 시도하고, 이 중에 비용이 최소인 것을 고르는 것입니다. 이는 백트래킹을 사용하여 구할 수 있습니다.

하지만 이 방법은 \(N\)과 \(K\)의 제한이 \(300,000\)으로 높기 때문에 제한시간 내에 실행할 수 없습니다. 더 빠른 방법을 찾아야 합니다.

발상을 조금 바꿔봅시다. \(N\)명을 \(N\)개 조로 나눈 상황에서 시작해 봅시다. 이때 비용 총합은 당연하게도 \(0\)입니다.

여기서 \(N-1\)개 조로 조를 줄이려면, 기존에 있는 인접한 조 2개를 합쳐서 새로운 조를 하나 만들어야 합니다. 어떤 조 2개를 골라야 할까요?

원생 \(i\)의 키를 \(A_i\)라 하고, 원생 \(i, i+1, ..., j-1, j\)가 있는 조를 다음과 같이 표기하겠습니다.

\[[A_i, A_j]\]

이러면 \(N\)개 조를 다음과 같이 표현할 수 있습니다.

\[[A_1, A_1], [A_2, A_2], [A_3, A_3], ..., [A_N, A_N]\]

만약 조 \([A_1, A_1]\)과 \([A_2, A_2]\)를 합쳐 새로운 조 \([A_1, A_2]\)를 만들면 조의 개수는 \(N - 1\)개가 되고, 비용의 총합은 \(A_2-A_1\)이 됩니다.

그러면 \(A_{i+1}-A_i\)중에 가장 작은 것을 고른다면 조의 개수가 \(N - 1\)개 일때 비용 총합이 최소가 될 것입니다!

비슷한 방법으로 생각해 봅시다. 조가 \(T\)개 있다고 하고, \(T\)개 조가 다음과 같다고 합시다.

\[[A_1, A_{x_1}], [A_{x_1 + 1}, A_{x_2}], ..., [A_{x_{T-2}+1}, A_{x_{T-1}}], [A_{x_{T-1}+1}, A_N]\]

이 중 임의의 인접한 조 2개를 다음과 같이 골랐다고 해봅시다. 편의상 \(p, q, r\)의 표현을 사용합니다.

\[[A_p, A_q], [A_{q+1}, A_r]\]

이 두 조를 합쳐 새로운 조 \([A_p, A_r]\)를 만들게 되면 조의 개수는 \(T-1\)개가 되고, 비용의 총합이 변하게 됩니다.

기존 비용의 총합을 \(S_{old}\), 새로운 비용의 총합을 \(S_{new}\)라 하면 다음이 성립합니다.

\[S_{new}= S_{old} + (A_r - A_p) - (A_q - A_p) - (A_r - A_{q + 1}) = S_{old} + A_{q + 1} - A_q\]

즉 두 조를 합치면 두 조가 인접하는 부분에 있는 두 원소의 차이만큼 비용의 총합이 증가하게 됩니다! 

\(A\)는 오름차순 배열이므로 모든 \(q\)에 대하여 \(A_{q + 1} - A_q >= 0\)이 성립합니다. 따라서 비용 총합은 조가 합쳐져도 절대로 감소하지 않습니다.

따라서, 인접한 원소 차이가 가장 작은 것들을 계속 골라서 그 차이를 비용 총합에 더해주면 됩니다.

여기서 생각해 봐야할 것이 있습니다. 이전에 \(A_{x+1}\)와 \(A_x\)의 차이를 더해줬다면 또 이 값을 더할 수 있을까요?

\(A_x\)와 \(A_{x+1}\)이 더해졌다는 것은 이 두 값이 합쳐진 조의 양 끝이 아닌 중간에 들어갔다는 것을 의미합니다. 따라서 이 값들은 다시 사용할 수 없습니다.

즉, 어떤 \(x\)에 대하여 \(A_{x+1} - A_x\)는 비용 총합에 단 한 번만 더할 수 있습니다.

이제 문제를 해결할 수 있습니다. 인접한 두 원소의 차이 \(A_2 - A_1, A_3 - A_2, ..., A_N - A_{N-1}\)를 구하고, 오름차순으로 정렬합니다.

조를 한번 합칠 때 마다 조의 개수가 1개 줄어들고, 조가 \(N\)개인 상태로 시작하므로 총 \(N - K\)번 조를 합쳐주면 \(K\)개 조를 얻을 수 있습니다.

따라서 방금 정렬한 값들 중 앞의 \(N - K\)개를 더해주면, 비용 총합의 최솟값을 구할 수 있습니다.

시간 복잡도는 정렬과 덧셈을 합해 총 \(O(N \log N + N - K) = O(N \log N)\)입니다.

코드 (C++)

#include <bits/stdc++.h>

#define fastio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;
typedef long long ll;

int main() {
    fastio;
    
    int n, k;
    cin >> n >> k;
    
    ll cost = 0;
    vector<ll> height(n);
    
    for (int i = 0; i < n; i++) {
        cin >> height[i];
    }
    
    vector<ll> diff(n - 1);
    
    for (int i = 0; i < n - 1; i++) {
        diff[i] = height[i + 1] - height[i];
    }
    
    sort(diff.begin(), diff.end());
    
    for (int i = 0; i < n - k; i++) {
        cost += diff[i];
    }
    cout << cost;
    return 0;
}
// BOJ 13164

문제 링크: https://acmicpc.net/problem/23830 

문제를 요약해봅시다.

• 총 \(N\)명의 학생들 중, 점수가 \(K\) 미만인 학생의 점수를 \(q\) 더해주고, 점수가 \(K + r\) 초과인 학생의 점수를 \(p\) 빼줍니다.
• 점수 총합이 \(S\) 이상인 가장 작은 \(K\)를 찾아야 합니다. 어떤 \(K\)도 이를 만족시킬 수 없다면 \(-1\)을 출력합니다.

가장 먼저 점수 총합을 \(S\) 이상으로 만들 수 없는지 부터 찾아봅시다.

어떤 학생의 점수가 \(K\)보다 낮다면 그 학생의 점수는 \(q\) 증가합니다. 만약 \(K\)가 엄청나게 커서 모든 학생의 점수가 \(q\)씩 증가하게 된다면 이 때가 점수 총합이 최대가 될 것입니다.

점수 총합이 최대임에도 불구하고 점수 총합이 \(S\)보다 작다면 \(-1\)을 출력해야 되겠죠. 식으로 쓰면 다음과 같습니다.

\[\sum_{i=1}^{N}A_i+Nq < S\]

만약 점수 총합의 최댓값이 \(S\)보다 크다면 어떻게 해야 할까요? 곰곰이 생각해보면 이 문제는 다음과 같은 성질이 있습니다.

• \(K\)가 작아질수록 점수가 \(p\)만큼 감소하는 학생이 늘어납니다.
• \(K\)가 작아질수록 점수가 \(q\)만큼 증가하는 학생이 감소합니다.

이를 종합하면 \(K\)가 작아지면 점수 총합도 작아지고, \(K\)가 커지면 점수 총합도 커지는 것을 알 수 있습니다.

즉, 이분 탐색을 사용할 수 있습니다! 이분 탐색을 이용해 점수 총합이 \(S\) 이상이 되도록 하는 \(K\)의 값을 찾아봅시다.

\(K\)의 범위는 \(A_i\)의 범위를 넘어가지 않으므로, 구간 \([0, 100001]\)을 탐색하면 됩니다.

이때 \(X = 100001\)이라 하겠습니다.

찾는 방법은 간단합니다. 두 가지 정도를 생각해 볼 수 있습니다.

1)

배열 \(A\)를 미리 정렬합니다. 매 탐색마다 \(K\)보다 작은 수의 개수와, \(K + r\)보다 큰 수의 개수를 각각 구해 점수 총합을 구합니다.

배열 \(A\)가 정렬되어 있으므로 수의 개수를 구하는 것은 \(A\)에서 \(K\), \(K + r\)이 등장하는 첫 번째 위치를 각각 찾는 것과 같습니다. 따라서 시간복잡도는 \(O(\log{N})\)입니다.

이 연산을 총 \(O(\log{X})\)번 반복하고, \(A\)를 1번 정렬하므로 총 시간복잡도는 \(O(\log{X} \log{N} + N \log{N}) = O(N \log{N})\)입니다.

2)

이분 탐색을 매번 시행할 때마다 \(A\)를 순회하면서 점수 총합을 계산합니다. 훨씬 쉽습니다.

크기 \(N\)인 배열을 매번 순회하므로 시간복잡도는 \(O(N \log{X})\)입니다.

두 방법 모두 넉넉한 시간 안에 통과할 수 있습니다.

여기서 주의해야 할 점이 하나 있는데요, 배열의 원소 개수가 최대 \(10^5\)이고 각 원소의 값도 최대 \(10^5\)이므로 32비트 정수 자료형으로는 오버플로우가 일어날 수 있습니다.

64비트 정수형인 long long을 사용하도록 합시다.