헬스장에서 일하는 몸짱 트레이너 라이언은 최근 손님들에게 불평을 많이 들었다. 그것은 옷을 갈아입는데 다른 사람과 너무 가까워서 옷을 갈아입기가 불편하다는 것이었다.
불만을 해결하기 위해 고민하던 라이언은 손님들의 예약시간을 참고해서 되도록이면 서로 멀리 떨어지도록 키를 나눠주기로 마음먹었다. 예를 들어, 락커들이 3x3 정사각형 모양으로 배치되어있고, 동시간대에 2명의 손님이 예약되어있다면 아래와 같이 락커를 할당하는 것을 고려해볼 수 있다.
라이언이 일하는 헬스장은 아래와 같은 상황이라고 가정하자.
락커는 정사각형으로 배치되어있고, 락커 사이에 옷을 갈아입을 공간이 있다. 단, 이 공간은 계산에서 제외된다.
락커 간 거리는 상하좌우는 1로, 대각선은 2로 계산한다.
손님들은 철저하게 예약시간에 맞춰 락커를 이용하고, 퇴실하는 시간까지 락커를 차지한다.
영업시간은 오전 10시부터 오후 10시까지이다.
헬스장은 예약제로 운영되므로 락커의 개수보다 더 많은 손님들이 동시간대에 몰리는 경우는 없다.
이런 조건에서 헬스장을 이용한 손님들 중 가장 가까웠던 손님 간의 거리는 얼마일까?
제한사항
입력 형식
입력은 정사각형 한 변의 길이n과 손님수m, 그리고 각 손님의 예약된 입실/퇴실 시간timetable로 주어진다. 제한조건은 다음과 같다.
0 < n <= 10
0 <= m <= 1,000
timetable은m × 2크기의 2차원 배열이다. 각 행은 손님의 입실시각과 퇴실시각이 분 단위로 환산된 값(t1, t2)가 들어있다.
t1,t2에 대해서는 다음 조건이 성립한다.600 <= t1 < t2 <= 1,320
출력 형식
할당된 락커들 간 거리 중 최소거리를 리턴한다. 손님 간에 이용 시간이 한 번도 겹치지 않을 경우에는0을 리턴한다.
풀이
입출력 예시
풀이
처음에 풀 때는 손님을 시간별로 하나하나 받아들여서 사람들을 최대한 멀리 배치하는 경우를 생각했다. 물론 뜻대로 되지를 않았다.
다른 분들의 도움을 받아 다음과 같은 과정으로 풀어야 한다는 것을 알게됐다.
1. 제일 많은 사람이 몰리는 시간대를 찾아 몇 명이 운동을 하는지를 구한다. 이때, 인원이 1명이면 0을 반환한다.
2. 최대 거리에서 부터 차근차근 줄여나가면서 락커룸을 할당한다.
3. 할당된 락커룸의 수와 1번에서 구한 사람의 수가 같으면 그 거리를 반환한다.
#include <vector>
#include <algorithm>
using namespace std;
// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int n, int m, vector<vector<int>> timetable) {
// 1. 제일 많은 사람이 몰리는 시간대를 찾아 몇 명이 운동을 하는지를 구한다. 이때, 인원이 1명이면 0을 반환한다.
vector<int> count(1321);
for (auto& time : timetable) {
for (int i = time.front(); i <= time.back(); i++) {
count[i]++;
}
}
int people = *max_element(count.begin(), count.end());
if (people <= 1) {
return 0;
}
// 2. 최대 거리에서 부터 차근차근 줄여나가면서 락커룸을 할당한다.
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>> lock({ {i, j} });
for (int y = i; y < n; ++y) {
for (int x = 0; x < n; ++x) {
if (y != i || x > j) {
bool canPush = true;
for (auto& p : lock) {
int dist = abs(p.first - y) + abs(p.second - x);
if (dist < d) {
canPush = false;
break;
}
}
if (canPush) {
lock.emplace_back(y, x);
// 3. 할당된 락커룸의 수와 1번에서 구한 사람의 수가 같으면 그 거리를 반환한다.
if (people == lock.size()) {
return d;
}
}
}
}
}
}
}
}
return 0;
}
