[SWEA] 벌꿀채취

[SWEA] 벌꿀채취

Problem URL : 벌꿀채취

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int map[10][10];
int d[10][10];
int n, m, c;

// 벌통이 겹치지 않게 고를 수 있는 모든 경우의 수 고려
int getMaxPrice() {
	int ans = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			for (int k = j + m; k <= n - m; k++) {
				ans = max(ans, d[i][j] + d[i][k]);
			}

			for (int a = i + 1; a < n; a++) {
				for (int b = 0; b < n; b++) {
					ans = max(ans, d[i][j] + d[a][b]);
				}
			}
		}
	}
	return ans;
}

// 해당 좌표(i,j)에서 얻을 수 있는 최대값을 재귀적으로 계산
int calc(int i, int j, int x, int sum, int val) {
	if (sum > c) {
		return 0;
	}
	if (x == m) {
		return val;
	}
	return max(calc(i, j + 1, x + 1, sum + map[i][j], val + map[i][j] * map[i][j]), calc(i, j + 1, x + 1, sum, val));
}

int main() {
	int TC;
	scanf("%d", &TC);

	for (int tc = 1; tc <= TC; tc++) {
		scanf("%d %d %d", &n, &m, &c);
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				scanf("%d", &map[i][j]);
				d[i][j] = 0;
			}
		}
		// M개의 연속된 벌통을 좌표(i,j)마다 선택한 것을 계산
		for (int i = 0; i < n; i++) {
			for (int j = 0; j <= n - m; j++) {
				d[i][j] = calc(i, j, 0, 0, 0);
			}
		}
		printf("#%d %d\n", tc, getMaxPrice());
	}
	return 0;
}