백준 17076번 망가진 데이터

문제

택희는 이번 대회에 사용하기 위해 그래프를 몇 개 만들었다.

택희의 그래프 데이터는 항상 아래의 형식을 따른다.

N M U1 V1 U2 V2 U3 V3 ... UM VM

위는 정점이 N개, 간선이 M개인 그래프 데이터로, 모든 Ui, Vi에 대해 1 ≤ Ui, Vi ≤ N을 만족하며, N과 M 뒤에 등장하는 간선 정보(U, V 페어)는 정확히 M개이다. 그 외의 다른 조건은 없다.

택희는 대회에 사용할 모든 그래프를 만들었고, 데이터를 업로드하려던 그 순간! 갑자기 영훈이가 나타나 데이터의 여기저기에 임의의 정수를 몇 개 써 넣어 버렸고, 택희는 순간적인 상황 변화를 받아들이지 못하고 격한 욕설을 내뱉으며 영훈이에게 당장 원래 데이터로 고쳐 두라고 말한 뒤 자리를 떠나 버렸다.

영훈이는 최대한 빠르게 그래프 데이터를 복원해야 한다. 하지만 자신이 어디에 어떤 수를 썼는지 전혀 기억하지 못하는 영훈이는 고민에 빠졌다.

영훈이는 자신이 데이터에 한 일은 수를 임의의 위치에 넣은 것뿐이라는 것을 알기에, 데이터에서 몇 개의 수를 지워 그래프 데이터를 만들려 한다. 즉, 수들의 원래 순서를 유지하면서 수 일부를 지워, 남은 수들이 '올바른 데이터' 가 되도록 하려는 것이다. 이때 '올바른 데이터' 란,

• 4개 이상의 정수로 이루어져 있고,
• 택희가 처음 만든 데이터의 형식을 따르며,
• 택희가 지키려 했던 모든 조건을 지키고 있는 데이터를 의미한다.

영훈이는 그래프를 복원할 방법이 여러 가지라면 기왕이면 노드의 수(N)가 가장 큰 것을, 그러한 것도 여러 가지라면 간선의 수(M)가 가장 큰 것을 복원할 것이다.

현재 데이터의 상태가 주어졌을 때, 영훈이가 복원할 그래프의 노드의 수와 간선의 수를 알아내보도록 하자.

문제풀이

사용한 알고리즘 : segtree

(0) 생각

 문제 조건을 만족하는 N, M이 될 수 있는 수를 뒤부터 탐색하면서 찾을 것입니다.

 각 탐색 시 조건을 만족하는 N, M이 되기 위해서는,

    1. 해당 수가 M이 되기 위해서는 해당 수 뒤에 최소 2*M개의 수가 있어야 합니다.

    2. M 앞의 N이 될 수는 M뒤의 2*M 번째로 작은 수 이상이어야 합니다. 

       ( M 뒤에서 무조건 작은 2*M개로 그래프 연결 관계를 생각한다. )  

 예를 들어  5 5 2 9 8 2 6 12 8 1 5 14 를 살펴보면,

    1]  5 5 2 9 8 2 6 12 8 1 5 14 경우

        14는 뒤에 적어도 2*14개의 수가 있어야 하는데 없다. (14는 M이 될 수 없다.)

    2]  5 5 2 9 8 2 6 12 8 1 5 14 경우

        5는 뒤에 적어도 2*5 개의 수가 있어야 하는데 없다. (5는 M이 될 수 없다.)

    3]  5 5 2 9 8 2 6 12 8 1 5 14 경우

        1은 뒤에 2*1 개의 수가 있으므로 M이 될 수 있다.

        1 뒤의 2*1 번째로 작은 수는 14 인데, 1 앞에 14이상의 수가 없다. 

        (N이 될 수 있는 수가 없다.)

    4]  5 5 2 9 8 2 6 12 8 1 5 14 경우

        8 뒤에 적어도 2*8개의 수가 있어야 하는데 없다. (8은 M이 될 수 없다.)

    5]  5 5 2 9 8 2 6 12 8 1 5 14 경우

        12는 뒤에 적어도 2*12개의 수가 있어야 하는데 없다. (12는 M이 될 수 없다.)

    6]  5 5 2 9 8 2 6 12 8 1 5 14 경우

        6은 뒤에 적어도 2*6개의 수가 있어야 하는데 없다. (6은 M이 될 수 없다.)

    7]  5 5 2 9 8 2 6 12 8 1 5 14 경우

        2는 뒤에 2*2 개 이상의 수가 있으므로 M이 될 수 있다.

        2 뒤에서 2*2번째 작은 수는 8이다.

        9는 8 이상이므로 N이 될 수 있다.

        따라서 N, M = 9, 2 로 찾을 수 있다.

        이때 그래프는 9 2 1 5 6 8 이라고 생각 가능합니다. (혹은 9 2 6 8 1 5)

    위 과정을 뒤에서부터 두번째 수까지 반복합니다.

    ( M이 가능한 수부터 탐색하므로 적어도 앞에 하나는 N이 될 수가 있어야 합니다.) 

(1) 코드 25~38

 뒤에서부터 탐색 하면서 보게 되는 수들을 차례로 segtree로 업데이트 해줍니다.

 이렇게 되면 i번째 탐색시, i+1~끝까지 수들은 segtree에 쌓여있습니다.

 i번째 수 탐색 시 i 뒤에서 2*(i번째 수) 번째로 작은 수를 찾게 해줍니다.

(2) 코드 7~24

 i번째 탐색 시, i번째 앞에 있는 수중 가장 큰 수를 찾는 segtree입니다.

(3) 코드 52~67

 뒤에서부터 차례로 탐색합니다.

 i번째 수 탐색 시, i 뒤에 2*(i번째 수) 만큼 수가 있는지 판단하고,

 이들 중 2*(i번째 수) 번째로 작은 수를 찾고,

 i앞에 '2*(i번째 수) 번째로 작은 수' 이상의 수가 있는지 확인합니다.