백준 1943 동전분배

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

1943번: 동전 분배

 

문제접근법 : 쉽게 풀었는데

시간초과해결할려고 2시간동안이나 해결못한 문제입니다.

무슨말이냐면 파이썬으로 풀다가 시간초과가 해결이안되서

c++로 풀었더니 c++에서는 같은코드인데도 통과가 되더군요 너무어이 어처구니 없어서 ㅠ.ㅠ 시간이 너무 낭비된꼴

배낭문제지만 c++ 에서는 

dp+메모이제이션으로 해결가능합니다.

파이썬은 안되더군요 

그리고 모든 동전으로 만들수있는 합이 홀수이면 절대로 이등분 할수없다는것은 쉬운사실이니

생략하고 그안에서 해결하면됩니다.

 

소스코드 : 

#include <bits/stdc++.h>
using namespace std;
int n,m;
vector<vector<int>> dp;
vector<pair<int,int>> v;
int sum=0;
void input(){
	cin>>n;
	v=vector<pair<int,int>>(n);
	sum=0;
	for(int i=0;i<n;i++){
		cin>>v[i].first>>v[i].second;
		sum+=v[i].first*v[i].second;
	}
}
int dfs(int cur,int cost){
	if(cost==0)return 1;
	if(cur>=n)return 0;
	int &cache = dp[cur][cost];
	if(cache != -1)return cache;
	for(int i=1;i<=v[cur].second;i++){
		if(i*v[cur].first<=cost)
			cache = max(cache,dfs(cur+1,cost-i*v[cur].first));
	}
	return cache = max(cache,dfs(cur+1,cost));
}
void solve(){
	if(sum%2){
		cout<<0<<"\n";
		return;
	}
	dp =vector<vector<int>>(n,vector<int>(sum/2+1,-1));
	cout<<dfs(0,sum/2)<<"\n";
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	//freopen("input.txt","r",stdin);
	for(int i=0;i<3;i++){
		input();
		solve();
	}
	
}

 

파이썬으로 해결하고싶엇는데 아 ㅠ.ㅠ 좀더 공부가 필요한것같습니다.

 

궁금한점 혹은 모르는점 어떤질문이든 댓글은 언제나 환영입니다.