백준 20303 할로윈의 양아치

문제 URL : https://www.acmicpc.net/problem/20303

20303번: 할로윈의 양아치

 

문제 접근법 : 

 

union & find + dfs dp(배낭문제) 문제입니다. 

한사람의 사탕을 뺏으면 그친구것도 동시에 뺏기는거니

집합으로 표현합니다.

 

그림으로 그리게되면

이러한 그림이 형성됩니다.

총4개의 집합이 만들어집니다.

그렇게이 (4,9) 가있는 집합과 (7,8)이 있는의 집합을 뺏어서 4명이갖고있는 사탕을뺏어서 57개를 만들수있습니다.

만약 어떠한 관계도 없을경우 

최악의경우 N집합이 형성될수도 있다는것을 알아야합니다.

 

dfs+ 메모이제이션을 이용했는데 최악의경우

dp 메모리가 30000*3000 까지 갈수있습니다. 

메모리가 너무커서 TLE 혹은 메모리 초과일줄알았는데 되긴되더군요 너무 간당간당했지만

 

소스코드 :

#include <bits/stdc++.h>
using namespace std;
int n,m,k;
vector<int> v,parent,setnum,cnt;
vector<pair<int,int>> pv;
vector<vector<int>> dp;
int find(int idx){
	if(parent[idx]==idx)return idx;
	return parent[idx]=find(parent[idx]);
}
void merge(int a,int b){
	a= find(a);
	b= find(b);
	if(a<b)parent[b]=a;
	else parent[a]=b;
}
void input(){
	cin>>n>>m>>k;
	cnt=setnum = parent =v= vector<int>(n);
	for(int i=0;i<n;i++)parent[i]=i;
	for(int i=0;i<n;i++)cin>>v[i];
	int a,b;
	for(int i=0;i<m;i++){
		cin>>a>>b;
		merge(a-1,b-1);
	}
}
int dfs(int sum,int cur=0){
	if(cur>=pv.size())return 0;
	int &cache = dp[sum][cur];
	if(cache != -1)return cache;
	if(pv[cur].second<sum){
		cache= max(cache,dfs(sum-pv[cur].second,cur+1)+pv[cur].first);
	}
	return cache = max(cache,dfs(sum,cur+1));
}
void solve(){
	for(int i=0;i<n;i++){
		setnum[find(i)]+=v[i];
		cnt[find(i)]++;
	}
	for(int i=0;i<n;i++){
		if(cnt[i]){
			pv.push_back({setnum[i],cnt[i]});
		}
	}
	dp = vector<vector<int>>(k+1,vector<int>(pv.size(),-1));
	cout<<dfs(k)<<"\n";
}
int main ()
{	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	//freopen("input.txt","r",stdin);
	input();
	solve();
}

 

지나치게 간당간당해서 시간을 줄이고자 생각했었고 배낭문제라 

방법은 똑같지만 재귀를 활용하지않고 풀면

메모리를 3000까지  사용하여 대폭줄일수있습니다.

 

소스코드 : 개선한코드

 

#include <bits/stdc++.h>
using namespace std;
int n,m,k;
vector<int> v,parent,setnum,cnt;
vector<pair<int,int>> pv;
vector<int> dp;
int find(int idx){
	if(parent[idx]==idx)return idx;
	return parent[idx]=find(parent[idx]);
}
void merge(int a,int b){
	a= find(a);
	b= find(b);
	if(a<b)parent[b]=a;
	else parent[a]=b;
}
void input(){
	cin>>n>>m>>k;
	cnt=setnum = parent =v= vector<int>(n);
	for(int i=0;i<n;i++)parent[i]=i;
	for(int i=0;i<n;i++)cin>>v[i];
	int a,b;
	for(int i=0;i<m;i++){
		cin>>a>>b;
		merge(a-1,b-1);
	}
}
void solve(){
	for(int i=0;i<n;i++){
		setnum[find(i)]+=v[i];
		cnt[find(i)]++;
	}
	for(int i=0;i<n;i++){
		if(cnt[i]){
			pv.push_back({setnum[i],cnt[i]});
		}
	}
	dp = vector<int>(k+1);
	for(int i=0;i<pv.size();i++){
		for(int j=k-1;j>=pv[i].second;j--){
			dp[j] = max(dp[j],dp[j-pv[i].second]+pv[i].first);
		}
	}
	int Max = 0;
	for(int i=0;i<k;i++)Max = max(dp[i],Max);
	cout<<Max<<"\n";
}
int main ()
{	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	//freopen("input.txt","r",stdin);
	input();
	solve();
}

궁금한점 혹은 모르는점  논리적인오류등 어떤 질문이든 댓글은 언제나 환영입니다.