💡 다이나믹 프로그래밍
Memory 18688KB Time 312ms Code Length 525B
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<stdio.h>
#include<algorithm>
using namespace std;
struct INFO {
int t;
int p;
};
INFO arr[1500001];
int memo[1500001];
int dp(int n) {
memo[1] = 0;
int ans = 0;
for (int i = 1; i <= n+1; i++) {
// 현재까지의 최대값
ans = max(ans, memo[i]);
if (i + arr[i].t > n + 1)continue;
memo[i + arr[i].t] = max(memo[i + arr[i].t],ans + arr[i].p);
}
return ans;
}
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf(" %d %d", &arr[i].t, &arr[i].p);
}
printf("%d", dp(n));
}
이 코드는 n일 동안의 일을 효율적으로 처리하여 얻을 수 있는 최대 이익을 계산하는 프로그램이다. 구조체 INFO는 각 일의 소요 시간과 보상을 나타내며, arr 배열에 저장된다. dp 함수는 동적 계획법을 사용하여 최대 이익을 계산하는 함수이다. memo 배열은 각 날짜별 최대 이익을 저장하는 배열이다.
main 함수에서는 사용자로부터 n일을 입력받고, 각 일의 소요 시간과 보상을 arr 배열에 저장한다. 그 후 dp 함수를 호출하여 최대 이익을 계산하고 출력한다.
