백준 7579 앱

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

7579번: 앱

 

문제 접근법 : 

dp문제이지만 어떻게 접근하냐에따라 메모리초과 혹은 시간초과를 겪어나 맞출수있는 문제입니다.

여러번의 메모리 초과 시간초과를 겪었고 힘들게 풀었네요

 

처음엔 메모리를 이용해서 최소비용을 구할려다가 시간초과가 나오고

메모리와 n을 이용하면 메모리 초과가나오고 

 

앱들과 비용을 이용해서 하면 100*10000 충분히 간으하더군요

백트래킹으로 메모이제이션을 이용하면

cost 0 부터 모든 cost의 합까지 조사해서 M 바이트를 확보가능하다면 바로 답을내서

종료하면됩니다.

 

소스코드:

#include <bits/stdc++.h>
using namespace std;
int n,m;
vector<vector<int>> dp;
vector<int> mem,cost;
int Sum=0;
int res =1e9;
void input(){
	cin>>n>>m;
	mem = cost= vector<int>(n);
	for(int i=0;i<n;i++)cin>>mem[i];
	for(int i=0;i<n;i++){
		cin>>cost[i];
		Sum +=cost[i];
	}
}

int dfs(int idx=0,int sum=Sum){
	if(idx>=n)return 0;
	int &cache = dp[idx][sum];
	if(cache !=-1)return cache;
	int l = dfs(idx+1,sum);
	if(cost[idx]<=sum)
		cache = max(cache,dfs(idx+1,sum-cost[idx])+mem[idx]);
	return cache= max(cache,l);
}
void solve(){
	dp = vector<vector<int>>(n,vector<int>(10001,-1));
	for(int i=0;i<=Sum;i++){
		if(dfs(0,i)>=m){
			cout<<i<<" ";
			break;
		}
	}

}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	//freopen("input.txt","r",stdin);
	input();
	solve();
	
}

 

궁금한점 혹은 모르는점 논리적인 오류등 어떤 질문이든

댓글은 언제나 환영입니다.