2115. [모의 SW 역량테스트] 벌꿀채취

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V4A46AdIDFAWu&categoryId=AV5V4A46AdIDFAWu&categoryType=CODE

SW Expert Academy

 

M개씩 뽑은 후에, 그 차례에서 그룹별로 최대 값 연산 수행 후 그 합의 비교를 수행해야 함.

 

#include<iostream>
#include<vector>
#include<string.h>
#include<cmath>
using namespace std;


int N, M, C;
int arr[10][10];
bool visit[10][10];
vector<int> a;
vector<int> b;
vector<int> sela;
vector<int> selb;
int maxa;
int maxb;
int result;

void finda(int idx, int cur)
{
	if (sela.size() == cur)
	{
		int cost = 0;
		for (int i = 0; i < cur; i++)
		{
			cost += sela[i];
		}
		if (cost > C)
		{
			return;
		}

		
		cost = 0;
		for (int i = 0; i < cur; i++)
		{
			cost += pow(sela[i],2);
		}
		if (maxa < cost)
		{
			maxa = cost;
		}

		return;
	}


	for (int i = idx + 1; i < a.size(); i++)
	{
		sela.push_back(a[i]);
		finda(i, cur);
		sela.pop_back();

	}
}

void findb(int idx, int cur)
{
	if (selb.size() == cur)
	{
		int cost = 0;
		for (int i = 0; i < cur; i++)
		{
			cost += selb[i];
		}
		if (cost > C)
		{
			return;
		}

		cost = 0;
		for (int i = 0; i < cur; i++)
		{
			cost += pow(selb[i], 2);
		}

		if (maxb < cost)
		{
			maxb = cost;
		}

		return;
	}

	for (int i = idx + 1; i < b.size(); i++)
	{
		selb.push_back(b[i]);
		findb(i, cur);
		selb.pop_back();

	}

}

void start()
{
	int sizea = a.size();
	int sizeb = b.size();

	maxa = 0;
	maxb = 0;


	for (int i = 1; i <= sizea; i++)
	{
		for (int j = 0; j < sizea; j++)
		{
			sela.push_back(a[j]);
			finda(j, i);
			sela.pop_back();
		}
	}


	for (int i = 1; i <= sizeb; i++)
	{
		for (int j = 0; j < sizeb; j++)
		{
			selb.push_back(b[j]);
			findb(j, i);
			selb.pop_back();
		}
	}

	if (result < maxa + maxb)
	{
		result = maxa + maxb;
	}

	
}



int main(int argc, char** argv)
{
	int test_case;
	int T;
	

	cin >> T;
	/*
	   여러 개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
	*/
	for (test_case = 1; test_case <= T; ++test_case)
	{

		cin >> N >> M >> C;
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				cin >> arr[i][j];
			}
		}


		memset(visit, 0, sizeof(visit));
		result = 0;

		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				if (!visit[i][j] && j + M - 1 < N)
				{
					if (!visit[i][j + M - 1])
					{
						for (int k = j; k <= j + M - 1; k++)
						{
							visit[i][k] = true;
							a.push_back(arr[i][k]);
						}

						for (int l = i; l < N; l++)
						{
							for (int m = 0; m < N; m++)
							{
								
								if (!visit[l][m] && m + M - 1 < N)
								{	
									if (!visit[l][m + M - 1])
									{
										for (int h = m; h <= m + M - 1; h++)
										{
											visit[l][h] = true;
											b.push_back(arr[l][h]);
										}
										start();
										for (int h = m; h <= m + M - 1; h++)
										{
											visit[l][h] = false;
											b.pop_back();
										}

									}
									
								}
							}
						}

						for (int k = j; k <= j + M - 1; k++)
						{
							visit[i][k] = false;
							a.pop_back();
						}
					}
				}
			}
		}

		cout << "#" << test_case << " " << result << endl;
	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}