글 읽기 - 풀이 방법 질문좀 하겠습니다..

njh0602 9년 전 0

하루종일 고민하고 풀어봤는데 자꾸 시간초과에 걸리네요.. 답은 맞게 나와서(?) 다행인데

최적화를 어디서 해야할지 모르겠습니다.. (아니면 애초에 접근법이 틀렸을 가능성도 있겠네요)

저의 풀이방법은

먼저 입력받은 데이터를 홀수와 짝수로 분리합니다. 그리고 모든 수를 더해봅니다.

Ex) 입력: 2, 3, 4, 6, 7, 8, 11, 15

첫번째수가 짝수이므로 짝수를 왼쪽에 배치함

(2, 4, 6, 8) | (3, 7, 11, 15)

2차원 배열을 만듭니다. (더하기연산)

5 9 13 17

7 11 15 19

9 13 17 21

11 15 19 24

이제 더해서 소수가 되는 경우를 찾을수 있습니다.

소수인지 판별은 에라토스테네스의 체 방법을 썼고 배열을 만들어서 값을 통해 0, 1을 얻어냅니다.

그래서 결국 (1은 소수, 0은 소수 아님)

1 0 1 1

1 1 0 1

0 1 1 0

1 0 1 0

이런 배열을 만들어냅니다.

그리고 각 행에서 하나씩 1을 뽑아낼 수 있으면 답을 구하는 식입니다. 한 번 뽑힌 열은 더 이상 쓸 수 없습니다.

재귀 함수를 이용하여 구현하였고, 뽑힌 열을 저장할 자료 구조는 std::list를 사용하였습니다.

그리고 재귀호출 갯수를 표준화시키기 위해(1 발견시 밑으로 재귀호출) 행을 1의 갯수를 기준으로 정렬했습니다.

Ex)

1 0 1 1 1 0 1 1

1 1 1 0 0 1 1 0

0 1 1 0 1 0 1 0

1 0 1 0 을 1 1 1 0

이렇게 바꿔놓고 재귀 함수를 돌립니다.

이 방법말고 근본적인 해결방법이 있는지 궁금합니다.

#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
#include <iterator>
#include <cmath>
using namespace std;

int n;
int **sample;
int *clear;
vector<int> vLeft;
vector<int> vRight;
vector<int> result;

void swapRow(int srcRow, int destRow)
{
	int tempRow[25] {0};
	for (int i = 0; i < n / 2; ++i)
		tempRow[i] = sample[srcRow][i];
	for (int i = 0; i < n / 2; ++i)
		sample[srcRow][i] = sample[destRow][i];
	for (int i = 0; i < n / 2; ++i)
		sample[destRow][i] = tempRow[i];
}

void checkArr(int y, list<int> useIdx, int answer,int startIdx)
{
	if (useIdx.size() == n / 2)
	{
		result.push_back(vRight[answer]);
		clear[answer] = 1;
	}
	if (clear[answer] == 1) return;
	if (y == n / 2) return;
	
	for (int i = startIdx; i < n / 2; ++i)
	{
		if (clear[answer] == 1) return;
		if (find(useIdx.begin(), useIdx.end(), i) != useIdx.end())
			continue;
		if (sample[y][i] == 1)
		{
			useIdx.push_back(i);
			checkArr(y + 1, useIdx, answer, 0);
			useIdx.erase(find(useIdx.begin(),useIdx.end(),i));
		}
		if (y == 0) i = n / 2;
	}
}

int main()
{
	cin >> n;
	int first; cin >> first;
	vector<int> p(n-1);
	for (int i = 0; i < n-1; ++i)
		cin >> p[i];

	vLeft.push_back(first);  // 왼쪽의 첫번째는 first가 들어간다.
	if (first % 2 != 0)		// 첫째수가 홀수면 left에는 홀수, right에는 짝수를 넣는다.
	{
		copy_if(p.begin(), p.end(), back_inserter(vLeft), [](int a){if (a % 2 != 0) return true; return false; });
		copy_if(p.begin(), p.end(), back_inserter(vRight), [](int a){if (a % 2 == 0) return true; return false; });
	}
	else					// 첫번쨰 수가 짝수면 left에는 짝수, right에는 홀수를 넣는다.
	{
		copy_if(p.begin(), p.end(), back_inserter(vLeft), [](int a){if (a % 2 == 0) return true; return false; });
		copy_if(p.begin(), p.end(), back_inserter(vRight), [](int a){if (a % 2 != 0) return true; return false; });
	}

	if (vLeft.size() != vRight.size()) // 홀, 짝 갯수가 다르면 답은 나올 수 없다.
	{
		cout << -1 << endl;
		return 0;
	}

	// 소수 판별용 배열을 만든다. (0 ~ 1999까지 판단)
	vector<int> prime;
	prime.assign(2000, 1);
	prime[0] = prime[1] = 0;
	for (int i = 2; i < (int)sqrt((double)2000); ++i)
		for (int j = i + i; j < 2000; j += i)
			prime[j] = 0;

	clear = new int[n / 2];
	for (int i = 0; i < n / 2; ++i)
		clear[i] = 0;

	sample = new int*[n / 2];
	for (int i = 0; i < n / 2; ++i)
		sample[i] = new int[n / 2];
	
	for (int i = 0; i < n / 2; ++i)
		for (int j = 0; j < n / 2; ++j)
			sample[i][j] = prime[vLeft[i] + vRight[j]];
	
	vector<int> rowCnt;
	vector<int> sortCnt;
	for (int i = 1; i < n / 2; ++i)
	{
		int cnt = 0;
		for (int j = 0; j < n / 2; ++j)
		{
			if (sample[i][j] == 1)
				cnt++;
		}
		rowCnt.push_back(cnt);
	}
	sortCnt = rowCnt;
	sort(sortCnt.begin(), sortCnt.end());

	for (int i = 0; i < n / 2 - 1; ++i)
	{
		if (sortCnt[i] != rowCnt[i])
		{
			int change = distance(rowCnt.begin(), find(rowCnt.begin()+i, rowCnt.end(), sortCnt[i]));
			swapRow(i+1, change+1);
			int temp = rowCnt[i];
			rowCnt[i] = rowCnt[change];
			rowCnt[change] = temp;
		}
	}

	list<int> useIdx;
	for (int i = 0; i < n / 2; ++i)
		checkArr(0, useIdx, i, i);

	if (result.size() == 0)
		cout << -1;
	else
		for (auto d : result)
			cout << d << " ";

	delete[] clear;
	for (int i = 0; i < n / 2; ++i)
		delete[] sample[i];
	delete[] sample;
}