Algorithm in A..Z - Programmers 몸짱 트레이너 라이언의 고민

https://programmers.co.kr/learn/courses/30/lessons/1838

코딩테스트 연습 - 몸짱 트레이너 라이언의 고민

---

접근

그리디하게 최대로 사람이 몰리는 시점에 사람이 몇명인지 파악하고 격자판에 그 사람을 배치하면 된다.

=> 사람이 많은 시점이 사람이 적은 시점보다 거리가 멀기 때문

 

1) 규칙성

격자판으로 채울 경우((n*n + 1)/2 == people)인 경우) 거리가 2, 그 이상은 거리가 1이라고 할 수 있다. 그 외에 경우 규칙성을 찾으려 했지만 실패

 

2) 분할정복 & DP

people이 1이면 0 (문제 조건)

people이 2면 2*n - 2 (양 끝 구석에 배치할 경우)

people이 4면 n - 1 (각 구석에 배치할 경우)

그리고 1)에서 알게된 조건으로 DP와 분할정복으로 해결하려고 했다.

격자판을 4등분하여 최대한 고르게 나눠서 분할하여 거리를 알아내는 방법

자세이 설명하면 n이 6이고 people이 8인 경우 격자판을 4등분한다(n이 3인 격자판 4개 생성) 그리고 각 격자판에 2, 2, 2, 2를 분배하고 거리가 낮은 경우를 채택

=> 분할한 격자판으로 얻은 결과가 독립적이지 못함.

 

3) 브루트 포스

일단 생각을 바꿨습니다. 최대한 사람을 많이 배치할 수 있는 방법을 찾는게 아닌. 각 거리별로 배치할 수 있는 최대의 사람을 찾는 것입니다. 최대로 많이 배치했을 경우 people과 같다면 그것이 답이기 때문입니다.

 

격자판의 최대 크기 100 (N^2)

최대거리 18(2N-2 양 끝 구석에 둘 경우)

최대 사람 1000 (M)

 

100 * 100 * 1000 * 18에서 가지치기를 잘하면 충분하다고 판단. 결국 성공

---

코드

#include <vector>
#include <algorithm>
using namespace std;

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int n, int m, vector<vector<int>> timetable) {
    vector<int> count(1321);
    for (auto &ve : timetable) {
        for (int i = ve.front();i <= ve.back();++i) {
            count[i]++;
        }
    }

    int people = *max_element(count.begin(),  count.end());
    if (people <= 1) {
        return 0;
    }

    for (int dis = 2*n - 2; dis > 0; --dis) {
        for (int i = 0;i < n;++i) {
            for (int j = 0;j < n;++j) {
                vector<pair<int, int>> ve({{i, j}});
                for (int y = i; y < n; ++y) {
                    for (int x = 0; x < n; ++x) {
                        if (y == i && x <= j) continue;

                        bool canPush = true;
                        for (auto &p : ve) {
                            int distance = abs(p.first - y) + abs(p.second - x);
                            if (distance < dis) {
                                canPush = false;
                                break;
                            }
                        }

                        if (canPush) {
                            ve.emplace_back(y, x);
                            if (people == ve.size()) {
                                return dis;
                            }
                        }
                    }
                }
            }
        }
    }

    return 0;
}