[BOJ/20665] 독서실 거리두기, c++

🔗 링크

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

20665번: 독서실 거리두기

🤯 한줄 후기

그냥 ㅡㅡ 독서실 가지마

🤷 문제

 

👩‍💻 풀이

대회 준비로 Shake! 2020 셋을 풀어보았다. 확실히 대학별 예선전을 거친 사람들만 나오는 대회다보니 문제가 어려웠다 :-(

대회 때 가장 많은 정답률을 보유했을 것 같은 A번 문제
아아 보기만해도 어지러워지는 문제이다. 힌트가 글도 길고 그림도 나오고
하지만 읽어보면 사실 n 수도 굉장히 작고 그냥 bruteforce 로 다 돌려보면 된다. 다만,, 구현이 조금 빡센편? 처음에 지레 겁을 먹고 그리디인가.. 하며 풀이 생각하는데 시간을 너무 쏟았다.
다양한 풀이 방법이 존재할 것 같은데 나는 timetable[h][m][seat] 3차원 배열을 만들어서 해당시간에 해당 seat에 앉아 있는 사람이 존재한다면 1로 체크하고, 마지막에 관리자가 앉을 수 있는 자리를 찾을 때는 timetable[h][m][P] 값이 0일 때마다 1분씩 추가해줬다.
time은 처음에 sort 해주었다. sort는 시작시간이 먼저인 사람부터, 그리고 종료시간이 더 짧은 사람부터.
seat를 고를때는 현재 시간대에 자리가 비어있는 모든 seat 마다 가장 가까이 있는 사람과의 거리를 구해 최종적으로 이 거리가 가장 먼 자리 번호를 골라주었다.
자리 번호가 나오면 이제 해당 사람의 start time ~ end time 까지 모든 timetable을 1로 바꿔주었다.
이 과정에서 사실 나는 굉장히 직관적으로 접근한거라 케이스를 많이 나눠줘야 했다. 더 좋은 방법이 있을 것 같다.

입력 시간 값이 4자리 숫자로 나오는데 /100, mod 100 연산을 통해 쉽게 시간과 분을 구할 수 있다.

💻 코드

//AC
//BOJ 20666 독서실 거리두기
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <tuple>
using namespace std;
int N, T, P;
int timetable[25][60][101];  // s, m, seat

struct Time{
    int startT;
    int startM;
    int endT;
    int endM;
};

bool cmp (const Time &a, const Time &b) {
    if (a.startT == b.startT) {
        if (a.startM == b.startM) {
            if (a.endT == b.endT) {
                return a.endM < b.endM;
            }
            return a.endT < b.endT;
        }
        return a.startM < b.startM;
    }
    return a.startT < b.startT;
}

auto distance(int index, int h, int m) {
    int distance = 987654321;
    int minIndex = 1;
    for (int i = 1; i <= N; i++) {
        if (index == i)  continue;
        if (timetable[h][m][i]) {
            int d = abs(index - i);
            if(distance > d) {
                distance = d;
                minIndex = i;
            }
        }
    }
    return tuple(distance, minIndex);
}

int findSeat (int h, int m) {
    int index = 1;
    int maxDis = 0; 
    for(int i = 1; i<=N; i++) {
        if (!timetable[h][m][i]) {
            auto[md, mi] = distance(i, h, m);
            if(md > maxDis) {
                maxDis = md;
                index = i;
            }
        }
    }
    return index;
}

vector<Time> v;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int a, b, res = 0;
    cin >> N >> T >> P;
    for(int i=0; i<T; i++) {
        cin >> a >> b;
        int sT = a / 100;
        int sM = a % 100;
        int eT = b / 100;
        int eM = b % 100;
        v.push_back({sT, sM, eT, eM});
    }
    sort(v.begin(), v.end(), cmp);
    for (Time t: v) {
        int sT = t.startT;  int sM = t.startM;
        int eT = t.endT;    int eM = t.endM;
        int idx = findSeat(sT, sM);
        for(int i = sT; i <= eT; i++) {
            if(sT == eT) {
                for(int j=sM; j < eM; j++) {
                    timetable[i][j][idx] = 1;
                }
                break;
            }
            if(i == sT) {
                for(int j=sM; j<=59; j++) {
                    timetable[i][j][idx] = 1;
                }
            }
            else if(i == eT) {
                for(int j=0; j<eM; j++) {
                    timetable[i][j][idx] = 1;
                }
            }
            else {
                for(int j=0; j<=59; j++) {
                    timetable[i][j][idx] = 1;
                }
            }
        }
    }
    for (int i = 9; i <= 20; i++) {
        for (int j = 0; j <= 59; j++)  {
            if (!timetable[i][j][P]) {
                res += 1;
            }
        }
    }
    cout << res;
    return 0;
}