백준 20665번 독서실 거리두기

🔒문제 url

https://www.acmicpc.net/problem/20665

🔑알고리즘

민규가 선호하는 좌석 번호 $p$에 사람들이 앉는 시간의 합을 구한 뒤,
$0900$ ~ $2100$을 분으로 환산한 720분에서 합을 빼준 값을 출력하면 된다.

1. 시간을 분으로 환산(ex : $0950 \to 770 =9 \times60+50$)하여 정렬
2. 입장 시간에 의해 오름차순 정렬된 각 회원이 앉게될 자리 탐색
   • 회원의 입장 시간 이전에 퇴실하는 회원 처리 (오름차순 우선순위 큐 이용)
   • 앉게될 좌석 번호가 $p$라면 (퇴실 시간 - 입장 시간)만큼 차감
3. 우선순위 큐에 회원의 퇴실 시간과 좌석 번호 삽입

🐾부분 코드

bool comp(pii a, pii b)
{
    if (a.first == b.first)
        return a.second - a.first < b.second - a.first;
    else return a.first < b.first;
}

[정렬 함수 구현]
입장 시간과 퇴실 시간을 삽입할 vector에 대한 정렬 함수이다.
입장 시간이 같다면 체류 시간을 기준으로, 다르다면 입장 시간을 기준으로 오름차순 정렬한다.

void INPUT()
{
    IAMFAST
    cin >> n >> t >> p;
    for (int i = 0; i < t; i++)
    {
        string a, b;
        cin >> a >> b;
        int h1, m1, h2, m2;
        h1 = stoi(a.substr(0, 2)) * 60;
        h2 = stoi(b.substr(0, 2)) * 60;
        m1 = stoi(a.substr(2));
        m2 = stoi(b.substr(2));

        v.emplace_back(h1 + m1, h2 + m2);
    }
}

[입력 및 환산]
string type의 시간을 분으로 환산하여 vector에 저장한다.

int getBestSeat()
{
    bool noPerson = true;

    int maxDist = 0, bestSeat = 1;
    for (int i = 1; i <= n; i++)
    {
        if (visited[i])
        {
            noPerson = false;
            continue;
        }

        for (int dist = 1; dist <= n; dist++)
        {
            int l = i - dist, r = i + dist;

            //L out, R out
            if (l < 1 && r > n) break;

            //L out, R in
            else if (l < 1 && r <= n)
            {
                if (!visited[r] && maxDist < dist) maxDist = dist, bestSeat = i;
                else if (visited[r]) break;
            }

            //L in, R out
            else if (l >= 1 && r > n)
            {
                if (!visited[l] && maxDist < dist) maxDist = dist, bestSeat = i;
                else if (visited[l]) break;
            }

            //L in, R in
            else if (1 <= l && r <= n)
            {
                if (!visited[l] && !visited[r] && maxDist < dist) maxDist = dist, bestSeat = i;
                else if (visited[l] || visited[r]) break;
            }

        }
    }

	//다른 좌석과 떨어져있는 경우가 없다면, 좌석 번호가 작은 곳으로
    if (maxDist == 0)
    {
        for (int i = 1; i <= n; i++)
            if (!visited[i])
            {
                bestSeat = i;
                break;
            }
    }

	//앉아있는 사람이 한 명도 없다면 1번 좌석을 선호한다.
    return ((noPerson) ? 1 : bestSeat);
}

[선호 좌석 번호 반환 함수]
특정 좌석 $i$을 기준으로 $dist$를 1씩 늘려가며 확인한다.
왼쪽과 오른쪽이 범위를 초과했는지 여부에 따라 조건식을 다르게 구현한다.
L out, R in의 경우, 오른쪽 방향의 좌석이 비었으면 통과이므로 조건식을 위와 같이 구현했다.

다른 좌석과 2칸 이상 떨어져있는 좌석이 없다면, 좌석 번호가 작은 곳으로 bestSeat을 갱신한다.

앉아있는 사람이 한 명도 없다면 1번 좌석을 반환한다.

void solution()
{
    sort(v.begin(), v.end(), comp);

    int ans = 720;

    for (auto T: v)
    {
        while (!pq.empty() && pq.top().first <= T.first)
        {
            visited[pq.top().second] = false;
            pq.pop();
        }

        int bestSeat = getBestSeat();
        if (bestSeat == p) ans -= T.second - T.first;

        visited[bestSeat] = true;
        pq.emplace(T.second, bestSeat);

    }

    cout << ans;
}

각 사람을 순회하며 좌석을 지정한다.
입장 이전에 퇴실할 사람이 존재하면 해당 좌석을 공석 처리한 후 입장을 처리한다.

입장하는 회원이 $p$에 앉게 된다면, 720으로 초기화해둔 ans에서 체류 시간만큼 뺀다.
이후, 퇴장 시간과 좌석 번호를 우선순위 큐에 삽입한다.

🪄전체 코드

#include <bits/stdc++.h>

using namespace std;
#define IAMFAST ios_base::sync_with_stdio(false);cin.tie(0);
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;

int n, t, p;
bool visited[101];

bool comp(pii a, pii b)
{
    if (a.first == b.first)
        return a.second - a.first < b.second - a.first;
    else return a.first < b.first;
}

vector<pii> v;
priority_queue<pii, vector<pii>, greater<>> pq;

void INPUT()
{
    IAMFAST
    cin >> n >> t >> p;
    for (int i = 0; i < t; i++)
    {
        string a, b;
        cin >> a >> b;
        int h1, m1, h2, m2;
        h1 = stoi(a.substr(0, 2)) * 60;
        h2 = stoi(b.substr(0, 2)) * 60;
        m1 = stoi(a.substr(2));
        m2 = stoi(b.substr(2));

        v.emplace_back(h1 + m1, h2 + m2);
    }
}

int getBestSeat()
{
    bool noPerson = true;

    int maxDist = 0, bestSeat = 1;
    for (int i = 1; i <= n; i++)
    {
        if (visited[i])
        {
            noPerson = false;
            continue;
        }

        for (int dist = 1; dist <= n; dist++)
        {
            int l = i - dist, r = i + dist;

            //L out, R out
            if (l < 1 && r > n) break;

            //L out, R in
            else if (l < 1 && r <= n)
            {
                if (!visited[r] && maxDist < dist) maxDist = dist, bestSeat = i;
                else if (visited[r]) break;
            }

            //L in, R out
            else if (l >= 1 && r > n)
            {
                if (!visited[l] && maxDist < dist) maxDist = dist, bestSeat = i;
                else if (visited[l]) break;
            }

            //L in, R in
            else if (1 <= l && r <= n)
            {
                if (!visited[l] && !visited[r] && maxDist < dist) maxDist = dist, bestSeat = i;
                else if (visited[l] || visited[r]) break;
            }

        }
    }

    if (maxDist == 0)
    {
        for (int i = 1; i <= n; i++)
            if (!visited[i])
            {
                bestSeat = i;
                break;
            }
    }

    return ((noPerson) ? 1 : bestSeat);
}

void solution()
{
    sort(v.begin(), v.end(), comp);

    int ans = 720;

    for (auto T: v)
    {
        while (!pq.empty() && pq.top().first <= T.first)
        {
            visited[pq.top().second] = false;
            pq.pop();
        }

        int bestSeat = getBestSeat();
        if (bestSeat == p) ans -= T.second - T.first;

        visited[bestSeat] = true;
        pq.emplace(T.second, bestSeat);

    }

    cout << ans;
}

int main()
{
    INPUT();
    solution();
}

🥇문제 후기

전체에서 빼는 방식이 아닌, 현재 시간에 따라 더해가는 방식으로 구현하다가 피눈물을 흘려 크나큰 삽질을 했다.
힘들고 괴로웠다.