몸짱 트레이너 라이언의 고민 [Lv. 3]

프로그래머스

헬스장에는 N * N 크기의 락커가 있고 M명의 사람이 옵니다. 헬스장 회원들에게 락커를 배정할 때 최대한 떨어지게끔 배치를 해달라고 컴플레인이 들어왔습니다. 사람들이 오는 시간과 나가는 시간을 배열로 입력 받을 때, 헬스장을 이용한 손님들 중 가장 가까웠던 손님 간의 거리는 얼마인지 구하시외.

 

풀이방법

우선적으로 구해야 하는 것은 헬스장 오픈부터 마감까지 겹치는 인원의 수가 얼마인지입니다.

오픈 시간은 600, 마감 시간은 1320이므로 1321 크기의 배열을 만든 후 timetable을 순회하여 인원의 수를 채워줬습니다.

vector<int> log(1321);
for (auto& time : timetable)
    for (int i = time[0]; i <= time[1]; i++)
        log[i]++;

int cnt = *max_element(log.begin(), log.end());
if (cnt <= 1)
    return 0;

 

최대로 겹치는 사람의 수를 찾았으니 N * N 크기에서 배치를 시작해봐야합니다.

배치를 할 때에는 거리를 정해두고 배치를 합니다. (거리 5로 배치를 했을 때 불가능하고 거리 4로 배치가 가능하다면 정답은 4)

최대 거리부터 시작하여 해당 거리로 겹치는 인원 수 만큼 배치가 가능한지 체크합니다.

    for (int d = 2*n-2; d > 0; d--)
    {
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                vector<pair<int, int>> use({{i, j}});
                for (int y = 0; y < n; y++)
                {
                    for (int x = 0; x < n; x++)
                    {

                        bool flag = true;
                        for (auto& p : use)
                        {
                            int dist = abs(p.first - y) + abs(p.second - x);
                            if (dist < d)
                            {
                                flag = false;
                                break;
                            }
                        }
                        
                        if (flag)
                        {
                            use.push_back({y, x});
                            if (cnt == use.size())
                                return d;
                        }
                    }
                }
            }
        }
    }