ALPS 내부대회 B번 - 연애고수 최용욱 풀이


연애고수 최용욱

ALPS 2020 1월 내부대회 B번
출제자: ALPS 최용욱
2020. 01. 31

서브 태스크


Index Constraints Time Complexity
TC #1 (15 points) k=0k = 0, 2N1042 \le N \le 10^4 O(N)O(N)
TC #2 (45 points) 2N1042 \le N \le 10^4 O(N2)O(N^2)
TC #3 (140 points) none\text{none} O(Nlog2pmax)O(N\log_{2} p_{max})

풀이


  • DP 점화식

DP[i]=maxj>i+kn{DP[j],if pipj DP[j]+pjpi,otherwise\text{DP}[i] = \max_{j \gt i+k}^{n}\begin{cases}\text{DP}[j], & \text{if }p_i \ge p_j \\\ \text{DP}[j] + p_j -p_i, & \text{otherwise}\end{cases}

Index Solution
TC #1 모든 미팅에 참석하는 것이 항상 이득입니다.
따라서 다음 미팅과의 차이를 계속해서 누적합을 취하면 해결할 수 있습니다.
TC #2 DP 점화식을 2중 for문을 이용해 구현함으로써 해결할 수 있습니다.
TC #3 세그먼트 트리 2개와 큐 1개를 이용해 구현할 수 있습니다.
세그먼트 트리의 리프 노드에는 가능한 모든 점수들을 인덱스로 하는 DP값이 들어있습니다.
첫번째 세그트리는 DP값만을 저장합니다. 이는 점화식의 첫 번째 조건에 해당할 때 사용합니다.
두번째 세그트리는 DP값에 자기 자신의 높이를 더한 값을 저장합니다. 이는 두 번째 조건에 해당합니다.
1개의 큐는 kk번의 추후 연산이 지난 뒤 세그먼트 트리 갱신을 하기 위해 값을 저장하는 용도로 사용됩니다.

정해 코드


  • TC #1

#include <cstdio>

using namespace std;

int N, k, res, tmp = 1e6;

int main(){
    scanf("%d %d", &N, &k);

    for (int i = 0; i < N; i++){
        int input;
        scanf("%d", &input);

        if(input > tmp)
            res += input - tmp;

        tmp = input;
    }

    printf("%d", res);

    return 0;
}

k=0k = 0인 경우, 모든 미팅을 참석하면 됩니다.

바로 다음 미팅이 이전 미팅보다 점수가 높으면 점수 차가 발생하기 때문에 이득이고, 이전 미팅보다 점수가 낮으면 이후의 점수 차를 기대할 수 있으며 리스크가 없기 때문에 항상 다음 미팅을 참석하면 된다는 것을 알 수 있습니다.

따라서 미팅 점수에 대한 입력을 받으면서 이전 미팅과 점수 차가 발생할 수 있으면 그 차이를 누적함으로써 해결할 수 있습니다. 첫 번째 미팅을 어떻게 처리해야 하는지에 관한 질문이 들어왔었지만, 문제 속에 이전에 참석한 미팅이라고 명시되어 있어 따로 명시를 하지는 않았습니다. 이 경우의 시간복잡도는 O(N)O(N)입니다.


  • TC #2

#include <cstdio>
#include <algorithm>

using namespace std;

int arr[(int)1e7], dp[(int)1e7], k, N, maxx = -1;

int main(){
    scanf("%d %d", &N, &k);

    for (int i = 0; i < N; i++){
        scanf("%d", &arr[i]);
    }

    for (int i = 0; i < N; i++){
        for (int j = i + k + 1; j < N; j++){
            if(arr[j] > arr[i]){
                dp[j] = max(dp[j], dp[i] + arr[j] - arr[i]);
                maxx = max(maxx, dp[j]);
            }
            else{
                dp[j] = max(dp[i], dp[j]);
            }
        }
    }

    printf("%d", maxx);
}

Bottom-up 방식으로 DP 점화식을 구현한 코드입니다. 아이디어는 ii번째 미팅을 나갔다고 가정했을 때, kk번 이후의 jj번 미팅을 다음에 참석한다고 하는 경우 얻을 수 있는 점수를 DP 배열에 기록하는 것입니다. 따라서 DP 배열에는 해당 미팅을 참석한 미팅 중 마지막 미팅이라고 생각했을 때 얻을 수 있는 최고의 점수가 기록됩니다. DP 배열 중 가장 높은 점수를 출력함으로써 문제를 해결할 수 있습니다. 이 경우의 시간복잡도는 O(N2)O(N^2)입니다.

해당 코드를 보면 jj의 한계를 NN까지로 잡아두었지만, 사실은 i+2k+1i + 2*k + 1까지만 봐도 됩니다. 아이디어는 TC #1에서 알 수 있듯이, 어떤 미팅을 나가는 것에 대해 리스크가 없다는 것에서부터 나옵니다.

이전에 참석한 미팅 ii, (kk 번의 미팅들), 어떤 미팅 pp, (kk 번의 미팅들), 가고자 하는 미팅 jj가 있다고 해봅시다.
그러면 첫 (kk 번의 미팅들) 중에서는 어떤 것도 갈 수 없습니다. 용욱이는 쉬어야 하니까요.
만약 jj 미팅에 참석하고자 했을 때, 미팅 pp를 가지 않을 이유가 없습니다. pp 미팅을 가더라도 jj를 갈 수 있고, pjp \le j면 점수가 이득이고 아니더라도 리스크가 없기 때문에 용욱이는 미팅 pp를 참석할 것입니다. 따라서, NN까지 돌 필요 없이 알고리즘을 최적화 할 수 있습니다.
하지만, 이는 kkNN보다 적은 경우에 한해 어느정도 시간 단축이 가능하지 적당히 큰 경우에는 시간 차이를 보이지 않습니다.


  • TC #3

#include <cstdio>
#include <algorithm>
#include <queue>

using namespace std;

const int SIZE = 1 << 15;
const int MAX = 1e4;
int arr[(int)1e7+10], k, N, maxx = -1;

struct SegTree
{
    int tree[SIZE];
    queue<pair<int, int> > q;

    SegTree()
    {
        fill(tree, tree + SIZE, 0);
    }

    int sum(int node, int l, int r, int a, int b)
    {
        if (r < a || b < l)
        {
            return 0;
        }
        if (a <= l && r <= b)
        {
            return tree[node];
        }
        return max(sum(node * 2, l, (l + r) / 2, a, b), sum(node * 2 + 1, (l + r) / 2 + 1, r, a, b));
    }

    void qupdate(int idx, int value)
    {
        q.push(make_pair(idx, value));
        if (q.size() == k + 1)
        {
            pair<int, int> tmp = q.front();
            update(1, 1, MAX, tmp.first, tmp.second);
            q.pop();
        }
    }

    int update(int node, int l, int r, int idx, int value)
    {
        if (idx < l || r < idx)
        {
            return tree[node];
        }
        if (l == r)
        {
            return tree[node] = value;
        }
        return tree[node] = max(update(node * 2, l, (l + r) / 2, idx, value), update(node * 2 + 1, (l + r) / 2 + 1, r, idx, value));
    }
};

SegTree sg1, sg2;

int main()
{
    scanf("%d %d", &N, &k);

    for (int i = 0; i < N; i++)
    {
        scanf("%d", &arr[i]);
    }

    for (int i = N - 1; i >= 0; i--)
    {
        int current = arr[i];
        if (i > N - k - 2)
        {
            sg2.qupdate(current, current);
        }
        else
        {
            int fst = sg1.sum(1, 1, MAX, 1, current);
            int snd = sg2.sum(1, 1, MAX, current + 1, MAX) - current;

            int value = max(fst, snd);
            sg1.qupdate(current, value);
            sg2.qupdate(current, value + current);

            maxx = max(maxx, value);
        }
    }

    printf("%d", maxx);

    return 0;
}

NN10610^6까지 주어졌을 때 시간 제한 내에 문제를 해결하기 위해서는 다른 방법이 도입되어야 합니다.

제가 올려드린 코드는 세그먼트 트리를 이용한 풀이입니다. 많은 분들이 제 문제에서 바나나 우유를 채굴해 가셨기 때문에, 세그먼트 트리에 대한 간략한 설명이 필요하다고 생각하여 짧게 설명을 드리겠습니다.

세그먼트 트리는 어떠한 구간의 연산을 하는 데에 사용되는 트리입니다. 이 연산은 교환법칙과 결합법칙이 성립한다면 어떤 것이든 가능합니다. 사용되는 연산의 예시로는 최댓값, 최솟값, 곱셈, 덧셈, 그리고 비트 연산이 있습니다.
구간의 합을 저장하는 세그먼트 트리 예시를 통해 설명을 드리면, 여러분이 128개의 숫자를 입력으로 받는다고 합시다.
그러면 이 트리의 최상단에 있는 루트 노드는, [1, 128]까지의 합을 저장합니다. 루트 노드의 자식은 서로서로 반씩 범위를 양분하여, [1, 64], [65, 128]까지의 합을 담당합니다. 쭉 범위를 분절시키다보면 언젠가는 자기 자신의 값만 저장하는 경우가 생깁니다. [1, 1]처럼 말이죠. 이런 식으로 범위를 "나누며" 구간의 대표값을 각 노드들이 저장하기 때문에 "Segment" tree라고 부릅니다. 자세한 설명을 하기에는 주어진 종이가 너무 작기에, 이 문제에서는 이 정도만 이해하셔도 풀이는 보시는 데에는 문제가 없을 것이라고 생각합니다.

DP[i]=maxj>i+kn{DP[j],if pipj DP[j]+pjpi,otherwise\text{DP}[i] = \max_{j \gt i+k}^{n}\begin{cases}\text{DP}[j], & \text{if }p_i \ge p_j \\\ \text{DP}[j] + p_j -p_i, & \text{otherwise}\end{cases}

코드를 보면서 풀이를 설명해 드리겠습니다.

각각 sg1, sg2 두 개의 세그먼트 트리를 준비합니다. 각각은 DP의 두 조건에 해당하는 정보를 저장합니다.
이 세그먼트 트리는 모두 리프노드의 인덱스가 개별 점수와 같습니다. 점수의 범위가 1p1041 \le p \le 10^4이므로, 1부터 10000의 인덱스를 같은 리프노드를 담는 세그먼트 트리를 만듭니다.
sg1에는 해당 점수의 미팅이 가질 수 있는 최대의 점수를 넣고, sg2에는 그 점수에 자신의 인덱스(즉, 미팅의 점수)만큼을 더해두었습니다. 세그먼트 트리의 구조체에 구현된 update 함수는 세그먼트 트리의 구간들을 갱신해주는 함수이고, qupdate는 여기에 Queue를 더해 kk번 이후에 이 값들이 갱신될 수 있도록 하는 함수입니다.

첫 번째 미팅부터 시작하여 kk번 이후의 값을 쭉 갱신해줬던 서브태스크 2번의 풀이와 달리, 마지막 미팅부터 시작합니다.
마지막 미팅부터 이제 본다고 가정하면, kk개는 뒤에 갈 수 있는 미팅이 없으므로 sg1에는 0, sg2에는 미팅의 점수(코드에서는 current)를 저장해주어야 합니다. 따라서 sg2qupdate를 하는 식으로 구현했습니다.
이제 kk개가 지나면, 지금부터 볼 미팅들은 뒤에 갈 수 있는 미팅이 있기 때문에, 이 때까지 조사한 미팅 중에서 점수를 얻어와야 합니다. DP식을 보시면 아시겠지만, 이는 이제 볼 미팅 ii의 점수, 즉 pip_i에 전적으로 달려있습니다.
sg1에서는 자신보다 점수가 작거나 같은, pip_i까지의 점수에 해당하는 미팅들을 보고, DP 식의 첫 조건인 DP[j]\text{DP}[j]를 구합니다.
sg2에서는 자신보다 점수가 높은 미팅들을 보고, 두 번째 조건의 DP[j]+pj\text{DP}[j] + p_j를 구한 뒤, current만큼 이를 빼줍니다.
이 두 수(fst, snd) 중 최댓값을 구한 뒤, 각각을 sg1, sg2의 조건에 맞게 qupdate를 하는 과정을 반복하면서, 그렇게 도출된 점수 중에서 최댓값을 출력하는 것으로 문제는 끝이 납니다. 이 경우의 시간복잡도는 O(Nlog2pmax)O(Nlog_2p_{max})입니다.

마치며


첫 대회 출제이다보니, 많은 문제들이 있었습니다. 출제 아이디어를 잡기도 힘들었고, 난이도가 적절한 지도 계속해서 의문이 들었고, 내부대회인데 참가자분들이 만족하실만한 퀄리티를 못 내면 어떡하지라는 고민도 있었습니다. 그래도 그나마 많은 분들이 혜자같은 저의 k=0k=0 부분문제를 도전해주셨기도 하고, 발문이 좀 자학개그다보니 재밌어하신 것 같아 첫 문제치고는 잘된 것 같기도 합니다.

대회 중에는 테스트 케이스가 약해서 제가 설명드린 최적화된 O(N2)O(N^2)로 서브태스크3까지 뚫리는 문제도 있었고, 잘못된 코드를 거르지 못하고 맞다고 나와서 참가자분께서 테스트 케이스를 추가해주시기도 했습니다. (감사드리고 또 죄송합니다 ㅠㅠ)

벌써 2020년도 1월의 막바지에 다다랐습니다. 신종 코로나 바이러스의 창궐 속에서 바나나 우유를 하나씩 드시며 집에서 아늑하게 코딩하시고, 부디 건강 조심하시길 바랍니다. 제 문제 많이 봐주셔서 감사드리고, 다음에는 바나나 우유와 관련된 문제로 찾아뵙겠습니다. 다시 한번 감사드립니다 😊