글 읽기 - 치킨배달 문제 제시된 테스트케이스 이외에도 확인했는데 틀렸습니다

hoyun293 5년 전 0

분명 저의 로직이 틀렸겠지만, 어떤 예외케이스가 있는지를 제 수준으로는 찾지 못하였습니다.

저는 먼저 각각의 치킨 가게에서 집들로부터 거리의 총합을 구한 뒤, 오름차순으로 정렬 한 뒤, 주어진 M개 만큼 치킨 가게를 선정하였습니다.

(집들로부터 가장 멀리있는 치킨 집을 폐쇠하기 위해)

그리고 각각의 집으로부터 주어진 M개의 치킨 가게중 가까운 치킨 집의 거리를 구하였습니다. (만약 M이 3일경우 3개의 치킨 집 중 가장 가까운 거리)

그리고 최종적으로 각각의 집으로부터 가장 가까운 치킨 거리를 더하였습니다.

브루트포스 방식으로 풀려고 시도하였습니다.

답변주시면 감사하겠습니다 ㅠ

	#include<iostream>
	#include<vector>
	#include<algorithm>

	using namespace std;
	int N, M;
	int map[51][51];
	
	struct Data {
		int y;
		int x;
		int dist;
	};

	bool compare(Data a, Data b)
	{
		return a.dist < b.dist;				// 오름차순
	}
	int abs(int num)
	{
		if (num < 0)
			return num*-1;
		else
			return num;
	}
	int main()
	{
		cin >> N >> M;
		int temp;
		vector<pair<int, int>> save_Vec;
		vector<Data>store_vec;

		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				cin >> temp;
				if (temp == 1)
				{
					save_Vec.push_back(make_pair(j, i));			// 집의 주소를 저장한다
				}
				map[i][j] = temp;
			}
		}
		int chicken_dist = 0;
		int dist;
		
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				if (map[i][j] == 2)
				{
					chicken_dist = 0;
					for (int k = 0; k < save_Vec.size(); k++)
					{
						dist = abs(i - save_Vec[k].second) + abs(j - save_Vec[k].first);
						chicken_dist += dist;
					}
					store_vec.push_back({i,j,chicken_dist});
				}
			}
		}
		// 최대 M개의 매장만 남긴다
		sort(store_vec.begin(), store_vec.end(), compare);
		
		int sum_temp;
		int total_sum = 0;
		int mini = 8764321;
			for (int j = 0; j < save_Vec.size(); j++)
			{
				mini = 8764321;
				for (int k = 0; k < M; k++)			// M개의 매장에서 최소 치킨 거리르 구한다
				{
					sum_temp = abs(save_Vec[j].second - store_vec[k].y) + abs(save_Vec[j].first - store_vec[k].x);

					mini = min(mini, sum_temp);
				}
				total_sum += mini;
			}
			cout << total_sum;
	}

klimmek55 5년 전 2

아래와 같은 경우에 안됩니다.

(5,1)과 (3,4)의 치긴집을 고르면 치킨 거리가 13인데,
(5,1) 치킨집에서 거리의 합보다 (4,3) 치킨집에서 거리의 합이 작아서 (4,3) 치킨집을 골라 15가 나오네요.

브루트포스라고 하면 보통 모든 경우를 다 확인하는걸 말하는데 이 코드는 그렇지 않네요.

hoyun293 5년 전 0

와... 감사합니다; 예외케이스 이걸발견하려고 했는데 생각이 도저히 안났는데

감사합니다!

그냥 모든 조합을 골라서 그중 가장 작은 치킨 거리를 고르는 방식으로 해야겠네요

다시 한 번 감사드립니다 :)

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

문제

문제

출처

ICPC

치킨배달 문제 제시된 테스트케이스 이외에도 확인했는데 틀렸습니다

hoyun293 5년 전 0

klimmek55 5년 전 2

hoyun293 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말