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

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<vector>
using namespace std;
#define NS 11
int map[NS][NS];
int D[NS][NS];
int N, M, C;
int ret;
int ret1[3];
struct Data {
	int y; int x;
};
vector<Data>v[3];
struct Honey {
	Honey() {
		int T;
		scanf("%d", &T);
		for (int t = 1; t <= T; t++) {
			init();
			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]);
				}
			}
			dfs(0, 0,1);
			printf("#%d %d\n", t, ret);
		}
	}
	void init() {
		memset(map, 0, sizeof(map));
		memset(D, 0, sizeof(D));
		for (int i = 1; i < 3; i++) {
			ret1[i] = 0x80000000;
		}		for (int i = 0; i <= 2; i++) {
			v[i].clear();
		}
		ret = 0x80000000;
	}
	void copy(int map[NS][NS], int cmap[NS][NS]) {
		for (int i = 0; i < NS; i++) {
			for (int j = 0; j < NS; j++) {
				cmap[i][j] = map[i][j];
			}
		}
	}
	bool safe(int y, int x) {
		return 0 <= y && y < N && 0 <= x && x < N;
	}
	bool able(int y,int x,int idx) {
		for (int i = 0; i < M; i++) {
			if (safe(y, x)&&D[y][x]==0) {
				D[y][x++] = idx;
			}
			else return 0;
		}
		return 1;
	}
	void gainHoney() {
		for (int i = 0; i < 3; i++) {
			v[i].clear();
		}
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (D[i][j] != 0) {
					v[D[i][j]].push_back({ i, j });
				}
			}
		}

		for (int i = 1; i < 3; i++) {
		ret1[i]=0x80000000;
		}
		dfs(0,0,0,1);//일번 벌꿀
		dfs(0,0,0,2);//이번 벌꿀
		if (ret < ret1[1] + ret1[2])ret = ret1[1] + ret1[2];
	}
	void dfs(int idx,int sum,int finalSum, int num) {//idx 1에 대해서 
		if (idx == M) {
			if (sum <= C) {
				if (ret1[num] < finalSum)ret1[num] = finalSum;
			}
			return;
		}
		dfs(idx + 1, sum + map[v[num][idx].y][v[num][idx].x],finalSum+((map[v[num][idx].y][v[num][idx].x])*(map[v[num][idx].y][v[num][idx].x])),num);
		dfs(idx + 1, sum,finalSum,num);
	}
	void dfs(int y, int x, int idx) {
		if (idx == 3) {
			gainHoney();
			return;
		}
		int cmap[NS][NS] = { 0, };
		for (int i = y; i < N; i++) {
			for (int j = x; j < N; j++) {
				copy(D,cmap);
				if (able(i,j,idx)) {
					dfs(y , x + 1, idx + 1);
				}
				copy(cmap, D);
			}
			x = 0;
		}
	}
}Honey;
int main(void) {
	return 0;
}

매소드를 오버리딩하면서 그냥 문제를 구현했는데 오버리딩이 중요한것이 아니고

이묹는 일단 포인트는 연구소 문제를 풀었다면 그 구역을 설정하는 방식이 있는데 그방식을 이용해서 벌집을 선택을 

1 1 2 2 

0 0 0 0

0 0 0 0

 

1 1 0 0

2 2 0 0

0 0 0 0

 

 1 1 0 0

 0 2 2 0 

 0 0 0 0

이렇게 구역 설정을 할 줄 알아야합니다. 그리고 그 구역에 대해서 부분 수열의 합중 C이하이고 

 

C이하인것중에 제곱의 합의 최댓값이 얼마인지 구하는 문제로 우선 저렇게 dfs 재귀를 이용해서 모든 경우를 세워주고

 

부분수열의 경우도 

5 개의  0 0 0 0 0 

이면 1인것의 배열의 값을 더한다 했을때 

1 0 0 0 0

0 1 0 0 0

0 0 1 0 0

0 0 0 1 0

0 0 0 0 1

1 1 0 0 0

이런식으로 모든 경우를 더해봐야 합니다. 그래도 또 한개의 dfs를 두고 부분수열의 합을 구했습니다.

그렇게해서 그냥 최댓값을 뽑아내면 되는 문제 정말 쉽지 않나요? 여러분들도 도전해보세요 안되시면 질문 해주세요