[14501] 퇴사

• 입력: 일수 N, N개의 걸리는 일과 금액
• 출력: 최대 금액
• 알고리즘: 동적계획법, Knapsack 알고리즘
• 소스코드
#define _CRT_SECURE_NO_WARNINGS #include <cstdio> #include <vector> #include <algorithm> #define plan pair<int, int> #define mp(x, y) make_pair(x, y) using namespace std; vector<int> cache; vector<plan> schedule; int benefit(int idx, int n) { if (idx >= n) return 0; int& ret = cache[idx]; if (ret != -1) return ret; ret = max(benefit(idx + 1, n), ret); if (idx + schedule[idx].first <= n) ret= max(ret, schedule[idx].second + benefit(idx + schedule[idx].first, n)); return ret; } int main() { int N; scanf("%d", &N); schedule = vector<plan>(N); cache = vector<int>(N, -1); for (int i = 0; i < N; i++) scanf("%d %d", &schedule[i].first, &schedule[i].second); printf("%d\n", benefit(0, N)); return 0; }

전형적인 Knapsack 알고리즘이다.