(2024-10-30) 1 문제 : 백준 - 13160 (최대 클리크 구하기)

 

이 문제는 알면 쉬운 문제이지만 모르면 어려운 그런 문제인 듯 하다. 항상 문제가 비슷비슷하게 나오지만, 모르면 풀기 어려운..

 

먼저, 각 선분의 시작점과 끝점을 모두 벡터에 넣어준다. pair로 하나의 벡터에 넣어주고, 다른 벡터에는 점을 하나씩 따로 넣어준다.

 

따로 넣어줄 때, 그냥 점의 위치만 넣는 것이 아니라 {점의 위치, int}의 형태의 페어로 넣어주어야 판다.

second인 int은 해당 점이 선의 시작점이냐 끝점이냐를 표시하는 것이다. 본인은 second가 0이면 시작점, 1이면 끝점으로 표시하였다.

 

그리고, 점을 넣은 벡터를 오름차순으로 sort해준다. 이후, 차례대로 점을 훑으며 second가 0이면 Count를 ++하고, second가 1이면 Count를 --해준다.

 

그러면서, Count의 최대값을 찾는 것이다. Count의 값이 현재 탐색하는 위치가 걸쳐있는 선분의 개수를 의미하기 때문이다. Count의 갱신을 조금이라도 최적화하기 위해, second가 0일 때에만 Count를 갱신해주어도 된다. 

 

이렇게 구한 Count가 출력해야 할 클리크의 크기 s가 된다. 하지만 우리는 크기만 구하는 것이 아니라 클리크의 정점을 모두 출력해야 한다.

 

이룰 위해, Count를 갱신할 때 추가적으로 Position을 구해줄 것이다. Position은 Count가 갱신되는 지점의 점 위치이다.

Count와 Positon을 구한 뒤에, 반복문을 한 번 더 돌아주면 되는데 이번엔 점을 넣은 벡터가 아니라 처음에 선분의 시작점, 끝점을 pair로 넣었던 벡터를 순회할 것이다.

 

우리가 구한 position이 걸쳐있는 선분의 인덱스를 구해서 출력할 것이기 때문이다. 벡터의 원소를 모두 순회하며 first <= position && position <= second 인 모든 인덱스를 출력해주면 된다.

#include <iostream>
#include <vector>
#include <algorithm>

void Init()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
}

int main()
{
    Init();

    int NumLine = 0;
    std::cin >> NumLine;

    std::vector<std::pair<int, int>> Lines(NumLine);
    std::vector<std::pair<int, int>> Position(NumLine * 2);

    for (int i = 0; i < NumLine * 2; i +=2)
    {
        int Start = 0, End = 0;
        std::cin >> Start >> End;

        Lines[i / 2] = { Start, End };

        Position[i] = { Start, 0 };
        Position[i + 1] = { End, 1 };
    }

    std::sort(Position.begin(), Position.end());

    int Answer = 0;
    int AnswerPosition = 0;

    int StartCount = 0;

    for (int i = 0; i < Position.size(); i++)
    {
        if (Position[i].second == 0)
        {
            StartCount++;

            if (StartCount > Answer)
            {
                AnswerPosition = Position[i].first;
                Answer = StartCount;
            }
        }
        else
        {
            StartCount--;
        }
    }

    std::cout << Answer << "\n";

    for (int i = 0; i < Lines.size(); i++)
    {
        if (Lines[i].first <= AnswerPosition && Lines[i].second >= AnswerPosition)
        {
            std::cout << i + 1 << " ";
        }
    }

    return 0;
}