글 읽기 - [c++] 예제와 질문게시판 TC에서는 다 맞는데 자꾸 틀렸다고 나오네요ㅠㅠ

noddown 5년 전 1

치킨집 5개 중에 폐업하지 않을 치킨집 수를 3개이면

1,1,1,0,0 으로 설정(0=폐점치킨집)하여 풀었습니다.

그리고 각 집마다 배달 가능한 치킨집(1인 치킨집) 중 최소 거리를 구하여 다 더하여 해당 치킨집 조합에서의 최소거리를 구한 뒤,

prev_permutation을 이용하여 1,1,1,0,0 의 이전 조합 순서로 바꿔가면서 가장 최소가 되는 치킨집 조합에서의 거리를 답으로 제시하였습니다.

다 맞게 푼 것 같은데 왜 틀리다고 나오는지 모르겠어요 확인 좀 부탁드려요ㅠㅠ

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <cstdio>

using namespace std;

int Factorial(int n)
{
	if (n == 1 || n == 0) {
		return 1;
	}
	return n * Factorial(n - 1);
}


int main()
{
	
	//변수 선언
	int n, m;
	cin >> n >> m;
	int map_position[51][51] = { 0, };
	int total_chicken_num = 0;
	int total_house_num = 0;

	//문제 정보 받아들임.
	for (int y = 0; y < n; y++) {
		for (int x = 0; x < n; x++) {
			int building_type;
			cin >> building_type;
			map_position[x][y] = building_type;

			if (building_type == 2)
			{
				total_chicken_num += 1;
			}

			if (building_type == 1)
			{
				total_house_num += 1;
			}

		}
	}

	// 치킨집과 집 위치 좌표 저장.

	int chicken_pos_x[13];
	int chicken_pos_y[13];
	int house_pos_x[100];
	int house_pos_y[100];


	int temp_chick_count = 0;
	int temp_house_count = 0;
	for (int y = 0; y < n; y++) {
		for (int x = 0; x < n; x++) {
			if (map_position[x][y] == 2)
			{
				chicken_pos_x[temp_chick_count] = x;
				chicken_pos_y[temp_chick_count] = y;
				temp_chick_count += 1;
			}

			if (map_position[x][y] == 1)
			{
				house_pos_x[temp_house_count] = x;
				house_pos_y[temp_house_count] = y;
				temp_house_count += 1;
			}

		}
	}

	// 계산하기 위한 vector 선언
	vector <int> select_chicken;
	for (int i = 0; i < total_chicken_num; i++)
	{
		if (i < m)
		{
			select_chicken.push_back(1);
		}
		else
		{
			select_chicken.push_back(0);
		}

	}


	int min_distance[100] = { 0 };
	int temp_distance[100] = { 0 };
	int max_distance = 10000;

	int combination_num = Factorial(total_chicken_num) / (Factorial(total_chicken_num - m) * Factorial(m));

    int final_min_distance = 10000;
    
	for (int k = 0; k < combination_num; k++)
	{

		for (int i = 0; i < total_house_num; i++) {
			min_distance[i] = 10000;
		}

		for (int i = 0; i < total_house_num; i++) {
			for (int j = 0; j < total_chicken_num; j++) {
				if (select_chicken[j] == 1) {
					temp_distance[i] = abs(house_pos_x[i] - chicken_pos_x[j]) + abs(house_pos_y[i] - chicken_pos_y[j]);
					if (temp_distance[i] < min_distance[i]) {
						min_distance[i] = temp_distance[i];
					}

				}
			}
		}

		int total_min_distance = 0;
		for (int i = 0; i < total_house_num; i++) {
			total_min_distance += min_distance[i];
		}

		if (total_min_distance < final_min_distance) {
			final_min_distance = total_min_distance;
		}
		prev_permutation(select_chicken.begin(), select_chicken.end());
	}

	cout << final_min_distance;

	return 0;
}

작성자입니다. 치킨집을 선택하기 위해 factorial을 써서 combination을 구현하여 combination 횟수만큼 for문 동작 시키는 부분이 의심이 갔었는데요. 이 부분을 do { } while(prev_permutation) 꼴로 고쳤더니 정답이라고 뜹니다. 원인은 찾았는데 왜 for문으로 combination 회수를 직접 정해주면 안 되는지 아시는 분 있나요? 제 머릿속으로는 완전히 동일한 방법이라고만 생각되네요ㅠㅠ

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

문제

문제

출처

ICPC

[c++] 예제와 질문게시판 TC에서는 다 맞는데 자꾸 틀렸다고 나오네요ㅠㅠ

noddown 5년 전 1

noddown 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말