💡 브루트포스 알고리즘/다이나믹 프로그래밍
Memory 2020KB Time 0ms Code Length 584B
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 <iostream>
using namespace std;
int N;
struct info {
int T, P;
};
info arr[16];
int dp[21]; // 최댓값 갱신
void init() {
cin >> N;
for (int i = 1; i <= N; i++) {
cin >> arr[i].T >> arr[i].P;
}
}
void solve() {
int max = 0;
for (int i = 1; i <= N+1; i++) {
max = max < dp[i] ? dp[i] : max;
dp[i + arr[i].T] = max + arr[i].P < dp[i + arr[i].T] ? dp[i + arr[i].T] : max + arr[i].P;
// 상담완료 날짜의 최대값 갱신 : 현재 날짜의 DP값에서 요금을 더한 값 or 해당 날짜의 dp값
}
cout << max;
}
int main() {
init();
solve();
}
init() 함수에서는 사용자로부터 N개의 정보를 입력받아 구조체 배열 arr에 저장한다.
solve() 함수에서는 최대값을 구하기 위해 반복문을 실행하면서 각 날짜마다 최대값을 갱신한다.
각 날짜마다 해당 날짜까지의 최대값을 저장하는 dp 배열을 사용하여 상담을 완료한 날짜의 최대값을 갱신한다. 마지막으로 최종적인 최대값을 출력한다.
