[Programmers] 몸짱 트레이너 라이언의 고민

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/1838

프로그래머스

n의 범위가 작기 때문에 적당한 가지치기를 진행하면 브루트 포스로 풀 수 있는 문제였습니다.

 

알고리즘은 아래와 같습니다.

0. 문제에서 핵심은 특정 시간대에 어떤 회원들이 운동을 하고 있는지가 아닌 제일 많이 몰리는 시간대에 총 몇 명이 운동하고 있는지입니다.

1. 주어진 timetable을 순회하면서 제일 많이 겹치는 시간대에 총 몇 명의 회원이 있는지 확인합니다.

1.1 1번에서 구한 회원 수가 1 이하일 경우 0을 반환하고 프로그램을 종료합니다.

2. 락커 간 거리는 맨해튼 거리를 따르기 때문에 최대 거리는 2 * n - 2입니다.

2.1 락커 간 거리의 기준을 최대 거리부터 1까지 점진적으로 감소시키면서 회원들의 락커를 각 락커 간의 거리가 해당 거리 이상인지 확인한 뒤 조건을 만족하면 락커를 배정합니다.

2.2  배정된 락커 수가 1번에서 구한 회원 수와 일치할 경우 해당 거리를 반환합니다.

 

	#include <vector>
	#include <algorithm>
	#include <climits>
	#include <iostream>
	using namespace std;
	const int MAX = 1320 + 1;
	int getDistance(pair<int, int> a, pair<int, int> b)
	{
	return abs(a.first - b.first) + abs(a.second - b.second);
	}
	bool canPlaceFurther(pair<int, int> coord, int maxDistance, vector<pair<int, int>> &people)
	{
	for (pair<int, int> p : people)
	{
	if (getDistance(p, coord) < maxDistance)
	{
	return false;
	}
	}
	return true;
	}
	// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
	int solution(int n, int m, vector<vector<int>> timetable) {
	int answer = 0;
	int numberOfPeople[MAX] = { 0, };
	int start = INT_MAX;
	int end = 0;
	for (vector<int> t : timetable)
	{
	for (int i = t[0]; i <= t[1]; i++)
	{
	numberOfPeople[i]++;
	start = min(start, i);
	end = max(end, i);
	}
	}
	int maxCrowded = 0;
	for (int i = start; i <= end; i++)
	{
	maxCrowded = max(maxCrowded, numberOfPeople[i]);
	}
	if (maxCrowded <= 1)
	{
	return 0;
	}
	for (int distance = 2 * n - 2; distance > 0; distance--)
	{
	for (int y = 0; y < n; y++)
	{
	for (int x = 0; x < n; x++)
	{
	vector<pair<int, int>> people;
	people.push_back({ y, x });
	for (int y2 = y; y2 < n; y2++)
	{
	for (int x2 = 0; x2 < n; x2++)
	{
	if (y2 == y && x2 <= x)
	{
	continue;
	}
	if (canPlaceFurther({ y2, x2 }, distance, people))
	{
	people.push_back({ y2, x2 });
	}
	if (people.size() == maxCrowded)
	{
	return distance;
	}
	}
	}
	}
	}
	}
	return answer;
	}

view raw .cpp hosted with ❤ by GitHub

 

개발환경:Visual Studio 2017

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~