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

문제 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V4A46AdIDFAWu

SW Expert Academy

 

코드 : 

#include <iostream>
#include <limits>

using namespace std;

int N, M, C;
int num[10][10];
bool check[10][10] = { false };
int honeySum = -2147483647 - 1;
int honeyTotal = 0;
int maxValue = 0;

// M개 벌꿀 중 가장 큰 값 구하기.
//line = 가로로 갈수있는 데드라인, i = 세로, j = 가로, sum = 벌꿀들의 합, mul = 금액
void test(int line, int i, int j, int sum, int mul)
{
	//탈출조건
	if (j > line || sum > C)
	{
		return;
	}
	//성공조건
	if (sum <= C)
	{
		if (honeySum <= sum && honeyTotal < mul)
		{
			honeySum = sum;
			honeyTotal = mul;
		}
	}
	//다음경우
	for (int c = j; c < line; c++)
	{
		test(line, i, c + 1, sum + num[i][c], mul + (num[i][c] * num[i][c]));
	}
}

//일꾼 A가 방문하지 않는 모든 경우의 계산
//i = 세로, max = 일꾼 A의 금액
void solution(int i, int max)
{
	//탈출조건
	if (i >= N)
	{
		return;
	}

	bool check2 = true;
	//다음경우
	for (int c = 0; c <= N - M; c++) // 다음 열 경우의 수
	{
		check2 = true;
		for (int l = 0; l < M; l++)
		{
			if (check[i][c + l])
			{
				check2 = false;
				break;
			}
		}
		if (check2)
		{
			honeySum = -2147483647 - 1;
			honeyTotal = 0;
			test(c + M, i, c, 0, 0);
			int v = max + honeyTotal;
			if (maxValue < v)
			{
				maxValue = v;
			}
		}
	}
	solution(i + 1, max); // 다음 행 경우의수
}

int main()
{
	int lc = 1;
	int loop;
	cin >> loop;

	while (lc <= loop)
	{
		cin >> N >> M >> C;

		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				cin >> num[i][j];
			}
		}
		int mul = 0;
		maxValue = 0;
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j <= N - M; j++)
			{
				mul = 0;
				//일꾼 A 가 방문
				for (int c = 0; c < M; c++)
				{
					check[i][c + j] = true;
				}
				honeySum = -2147483647 - 1;
				honeyTotal = 0;
				test(j + M, i, j, 0, 0); //일꾼 A가 방문한것에 대한 벌꿀 mul값
				mul = honeyTotal;

				solution(0, mul);

				//일꾼 A  나옴
				for (int c = 0; c < M; c++)
				{
					check[i][c + j] = false;
				}
			}
		}
		cout << "#" << lc << " " << maxValue << "\n";
		lc++;
	}
	return 0;
}

 

이 문제를 풀면서 정말 다시 문제를 잘 읽어야 한다는 것을 또 느꼈다...

문제를 잘 읽고 이해한 대로 조건문들을 잘 구현했는지 확인하는 작업을 거쳐야겠다.

여기서 여러웠던 점은

1. 구현능력이 아직 미숙하다는 것.

2. 문제를 이해는 하였지만 구현할때 실수한것.

if (honeySum <= sum && honeyTotal < mul) 코드에서  honeyTotal < mul을 누락되어서 50개의 테스트 케이스 중 49개만 통과해서 Fail을 맞아버렸다... 

운 좋게 심기일전하여 간신히 찾았다.. 진짜 운이 좋았다..

다 풀고보니 main 함수의 solution(0, mul);에서 첫번째 인자를 0으로 설정할 필요가 없었다. 

내 생각에는 일꾼 A가 간것을 빼고 모든 경우의 수를 구해야 해서 0번째 행부터 즉 처음부터 구해야한다고 생각했는데 생각해보니 이미 앞에서 계산을 한 것들이라는 것을 실제로 해보니 알게되었다...

다행이 시간은 충분해서 pass가 뜬듯;;;