[swea 2115] 벌꿀 채취

분류 

브루트 포스, 구현

요구사항

모든 조건에서 구현하기 위하여 될 수 있는 꿀벌 칸은 모두 골라본다

 

풀이

모든 조건에서 구현하기 위하여 될 수 있는 꿀벌 칸은 모두 골라본다

고른 후, 최소 합을 구할 수 있도록 index를 고른다

->dfs로 미리 index의 순서를 구해 놓는다

모두 고른 후, combination을 실시할 경우 중복되는 일을 많이 한다

 

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

int n,m,c;
int map[11][11];
int ans=0;
int visit[11];
vector<vector<int>> v;
void dfs(int cnt, int now){
	if(now==m){
		vector<int> temp;
		for(int i=0 ; i < m ; i++){
			if(visit[i]==1){
				temp.push_back(i);
			//	cout<<i<<" ";
			}
		}
	//	cout<<endl;
		v.push_back(temp);
		return;
	}
	visit[now]=1;
	dfs(cnt,now+1);
	visit[now]=0;
	dfs(cnt,now+1);
}
int get_sum(int r, int c1, int c2){
	int nowans=0;
	for(int i=0 ; i <v.size() ; i++){
		int flag=0;
		int tempsum=0;
		int tempans=0;
		for(int j=0; j <v[i].size() ; j++){
			tempsum+=map[r][c1+v[i][j]];
		}
		if(tempsum<=c){
			for(int j=0; j <v[i].size() ; j++){
			tempans += (map[r][c1+v[i][j]]*map[r][c1+v[i][j]]);
			}	
		}
		nowans=max(tempans,nowans);
	}
	return nowans;

}
void solve(int sr1, int sc1, int sc2, int er1, int ec1, int ec2, int cnt){
	int tempc=sc2+1;
	//두개 다 골라졌다
	if(cnt==2){
		int sum1 = get_sum(sr1,sc1,sc2);
		int sum2 = get_sum(er1,ec1,ec2);
		int tempsum = sum1 + sum2;
		ans=max(tempsum,ans);
		return;
	}
	for(int i=sr1 ; i<n ; i++){
		for(int j= tempc ; j<n ; j++){
			if(j + m-1 <n){
				solve(sr1,sc1,sc2,i,j,j+m-1,cnt+1);
			}
		}
		tempc=0;
	}
}


int main(){
	int t;
	scanf("%d",&t);
	for(int tc=1;tc<=t;tc++){
		ans=0;
		memset(visit,0,sizeof(visit));
		v.clear();
		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);

		for(int i=0 ; i < n ; i++){
			for(int j=0 ; j < n ; j++){
				if(j + m-1 <n){
					solve(i,j,j+m-1,0,0,0,1);
				}
			}
		}
		printf("#%d %d\n",tc,ans);
	}
}