[SWEA] #2115 _ 벌꿀채취

[벌꿀채취] https://swexpertacademy.com/main/code/problem/problemDetail.do

SW Expert Academy

총 최대 이익은 일꾼1과 일꾼2의 각각의 최대 이익의 합이다.

따라서, max1에는 일꾼 1의 최대 값, max2는 일꾼 2의 최대 값을 저장하였다.

 

최대 3개의 벌통을 채취할 수 있다고 가정할 때,

각 벌통은 1. 채취하는 경우와 2. 채취 하지 않는 경우 두 가지를 고려할 수 있다.

chk배열을 이용하여 두 가지 경우를 고려하여 최대 이익을 구해주었다.

 

해당 문제는 dfs를 이용하여 쉽게 구현하였다.

 

[ 소스 코드 ]

#include <cstdio>
#include <vector>
#include <algorithm>
#define MAX 10

using namespace std;

int N, M, C, max1, max2, profit, limit, tmp;
int honey[MAX][MAX], chk[5];
vector<int> sel_honey;

void solve(int y, int x);
void getMaxValue(int idx);
int main() {
	int T;

	scanf("%d", &T);
	for (int i = 1; i <= T; i++) {
		scanf("%d %d %d", &N, &M, &C);
		for (int j = 0; j < N; j++) {
			for (int k = 0; k < N; k++) {
				scanf("%d", &honey[j][k]);
			}
		}
		
		limit = N - M;
		profit = 0;
		for (int j = 0; j < N; j++) {
			for (int k = 0; k <= limit; k++) {
				max1 = 0;
				max2 = 0;
				tmp = 0;
				solve(j, k);
				if (j == N - 1 && k >= N - (2 * M)) break;
			}
		}

		printf("#%d %d\n", i, profit);
	}

	return 0;
}

void solve(int y, int x) {
	int tmp_x = x, tmp_y = y;

	while (1) {
		sel_honey.push_back(honey[tmp_y][tmp_x++]);
		if (sel_honey.size() >= M) { // 일꾼 1
			getMaxValue(0);
			max1 = tmp;
			tmp = 0;
			sel_honey.clear();
			break;
		}
	}

	while (1) { // 일꾼 2
		if (sel_honey.size() == 0 && tmp_x > limit) {
			if (tmp_y >= N - 1) return;
			tmp_x = 0;
			tmp_y++;
			continue;
		}
		else sel_honey.push_back(honey[tmp_y][tmp_x++]);

		if (sel_honey.size() >= M) {
			getMaxValue(0);
			max2 = tmp;
			tmp = 0;
			profit = max(profit, max1 + max2);
			tmp_x -= (M - 1);
			sel_honey.clear();
		}
	}
}

void getMaxValue(int idx) {
	if (idx >= M) {
		int val = 0, chk_val = 0;
		for (int i = 0; i < M; i++) {
			if (chk[i]) {
				chk_val += sel_honey[i];
				if (chk_val > C) return;
				val += (sel_honey[i] * sel_honey[i]);
			}
		}
		tmp = max(tmp, val);
		return;
	}

	chk[idx] = 1;
	getMaxValue(idx + 1);
	chk[idx] = 0;
	getMaxValue(idx + 1);
}