글 읽기 - 치킨배달 시간초과 문제

qahira 4년 전 0

시간초과가 나는데 왜나는질 모르겠습니다...

치킨집을 M개씩 재귀로 중복없이 뽑고,

M개 뽑은 후에

집별로 뽑힌 치킨집 전부와 비교해서 집별로 최단거리를 구하고

모든 집들의 최단거리를 합해서 최단치킨 거리인가를 판단했는데,

알고리즘을 제가 잘못 계획한걸까요?ㅠㅠ

ps. 48~52 줄은 제대로 뽑나 확인하려구 넣은 코드입니다.제출할땐 빼ㅗㄱ 했어요

#include <iostream>
#include <cmath>
#include <climits>
#include <vector>

using namespace std;

struct point
{
	int r;
	int c;
};

vector<point> chicken;
vector<point> house;
vector<point> picked_chicken;
bool picked[13];

int N, M;
int min_dist = INT_MAX;
void pick(int m);
inline int distance(point p1, point p2);

int main(void)
{
	cin >> N >> M;
	int o;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			cin >> o;
			if (o == 2)
				chicken.push_back({ i,j });
			else if (o == 1)
				house.push_back({ i,j });
		}
	}
	pick(0);
	cout << min_dist << "\n";
	return 0;
}

void pick(int m)
{
	if (m >= M)
	{
		cout << "picked:\n";
		for (size_t i = 0; i < picked_chicken.size(); i++)
		{
			cout << picked_chicken[i].r << "," << picked_chicken[i].c << "\n";
		}
		int house_min = INT_MAX;
		int dist;
		int picked_dist = 0;
		for (size_t i = 0; i < house.size(); i++)
		{
			house_min = INT_MAX;
			for (size_t j = 0; j < picked_chicken.size(); j++)
			{
				dist = distance(house[i], picked_chicken[j]);
				house_min = house_min < dist ? house_min : dist;
			}
			picked_dist += house_min;
		}
		min_dist = min_dist < picked_dist ? min_dist : picked_dist;

		return;
	}

	for (size_t i = picked_chicken.size(); i < chicken.size(); i++)
	{
		if (!picked[i])
		{
			picked_chicken.push_back(chicken[i]);
			picked[i] = true;
			pick(m + 1);
			picked[i] = false;
			picked_chicken.pop_back();
		}
	}
}
inline int distance(point p1, point p2)
{
	return abs(p1.c - p2.c) + abs(p1.r - p2.r);
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

치킨배달 시간초과 문제

qahira 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말