백준 1535 안녕

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

1535번: 안녕

 

문제 접근법 : 

전수조사 or DP 문제입니다.

저같은경우는 재귀함수로 전수조사로 필요없는 부분을 메모이제이션을 활용했지만

n=20 인지라

메모이제이션을 활용안해도 상관없을정도로 빠르게 나옵니다. 20이기에

탐색 깊이가 100만까지는 충분히 커버가 가능해서

 

 

소스코드:

dfs+메모이제이션

#include <bits/stdc++.h>
using namespace std;
int n,m;
vector<int> damage,happy;
vector<vector<int>> dp;
void input(){
	cin>>n;
	damage = happy = vector<int>(n);
	for(int i=0;i<n;i++)cin>>damage[i];
	for(int i =0;i<n;i++)cin>>happy[i];

}
int dfs(int idx=0,int hp=100){
	if(idx>=n)return 0;
	int &cache = dp[idx][hp];
	if(cache!=-1)return cache;
	
	cache = max(cache,dfs(idx+1,hp));
	
	if(hp>damage[idx])cache = max(cache,dfs(idx+1,hp-damage[idx])+happy[idx]);
	return cache;
}
void solve(){
	dp =vector<vector<int>> (n,vector<int>(101,-1));
	cout<<dfs()<<"\n";
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	//freopen("input.txt","r",stdin);
	input();
	solve();
	
}

 

dfs 전수조사

#include <bits/stdc++.h>
using namespace std;
int n,m;
vector<int> damage,happy;
vector<vector<int>> dp;
void input(){
	cin>>n;
	damage = happy = vector<int>(n);
	for(int i=0;i<n;i++)cin>>damage[i];
	for(int i =0;i<n;i++)cin>>happy[i];

}
int dfs(int idx=0,int hp=100){
	if(idx>=n)return 0;
	//int &cache = dp[idx][hp];
	//if(cache!=-1)return cache;
	int cache=0;
	cache = max(cache,dfs(idx+1,hp));
	
	if(hp>damage[idx])cache = max(cache,dfs(idx+1,hp-damage[idx])+happy[idx]);
	return cache;
}
void solve(){
	dp =vector<vector<int>> (n,vector<int>(101,-1));
	cout<<dfs()<<"\n";
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	//freopen("input.txt","r",stdin);
	input();
	solve();
	
}

 

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