#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <set>
#include <deque>
#include <numeric>
#define ll long long
#define ull unsigned long long
using namespace std;
int N,ans;
vector<pair<int,int>> v;
void DFS(int depth, int left, int sum){
if(depth >= N) return;
for(int i=depth;i<N;i++)
{
left--;
if(left > 0) continue;
if(i+v[i].first > N) continue;
ans = max(ans, sum+v[i].second);
DFS(i+1, v[i].first, sum+v[i].second);
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> N;
for(int i=0;i<N;i++)
{
int a,b;
cin >> a >> b;
v.push_back({a,b});
}
DFS(0, 0, 0);
cout << ans;
return 0;
}
- 핵심
DFS
의 매개변수
로 left를 전달
해서 left가 0보다 작을 때 일을 하도록 설계
N이 15정도
로 작기 때문
에 충분히 완전탐색 으로 가능
한 것을 캐치
해야 함
#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <set>
#include <deque>
#include <numeric>
#define ll long long
#define ull unsigned long long
using namespace std;
int N,ans;
int DP[20];
vector<pair<int,int>> v;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> N;
v.push_back({-1,-1});
for(int i=0;i<N;i++)
{
int a,b;
cin >> a >> b;
v.push_back({a,b});
}
for(int i=2;i<=N+1;i++)
{
int MAX=0;
for(int j=1;j<i;j++)
{
if(j+v[j].first <= i)
MAX = max(DP[j] + v[j].second, MAX);
}
DP[i] = MAX;
}
cout << DP[N+1];
return 0;
}
- 로직
DP[i] = i일 전까지 일했을 때 얻는 최대 금액
DP[i]
는 1일 ~ i-1일
에 주어진 일
을 할 때 i일 전에 끝낼 수 있다면
그 중 최대값
을 의미
ex)
DP[4]
= 1일 일을 했을 때
, 2일 일을 했을 때
, 3일 일을 했을 때
총 3가지 경우중 최대
를 가짐
DP[4]
= max(DP[1]+v[1].second
, DP[2]+v[2].second
, DP[3]+v[3].second
);
- 핵심
: DP[i]를
i일 까지 일했을 때
로 잡을건지, i일 전 까지 일했을 때
로 잡을것인지 확실하게 정해야 함