반응형
https://www.acmicpc.net/problem/15486
15486번: 퇴사 2
첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000)
www.acmicpc.net
[ 문제풀이 ]
1. 각 날에 벌 수 있는 최대 금액을 저장할 dp배열을 만듭니다.
2. 각 날의 정보를 저장할 arr배열을 만듭니다.
3. for문을 통해 첫날부터 N번 째 날까지 dp [ i + t ] < dp [ i ] + p 라면 dp [ i + t ] = dp [ i ] + p를 적용시켜줍니다.
4. 매 날마다 최댓값을 갱신해주고, 만약 최댓값보다 낮은 금액을 번 날이 있다면 최댓값으로 갱신해줍니다.
5. 최댓값을 출력해줍니다.
[ 소스코드 ]
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 32 33 34 35 | #include<iostream> using namespace std; int N; int dp[1500001]; //각 날에 벌 수 있는 최대 금액을 저장할 dp배열 pair<int, int> arr[1500001]; //각 날의 정보를 저장할 배열 int main() { scanf("%d", &N); for (int i = 0; i < N; i++) { int t, p; scanf("%d %d", &t, &p); arr[i] = { t,p }; } int Max = 0; for (int i = 0; i <= N; i++) { int t = arr[i].first; int p = arr[i].second; Max = max(dp[i], Max); if (dp[i] < Max) { dp[i] = Max; } if (i + t > N) continue; if (dp[i + t] < dp[i] + p) { dp[i + t] = dp[i] + p; } } printf("%d", Max); } | cs |
반응형
'백준' 카테고리의 다른 글
| [ 백준 ] 2636번 - 치즈 (C++) (0) | 2022.10.16 |
|---|---|
| [ 백준 ] 3954번 - Brainf**k 인터프리터 (C++) (0) | 2022.10.15 |
| [ 백준 ] 14442번 - 벽 부수고 이동하기 2 (C++) (0) | 2022.10.13 |
| [ 백준 ] 17472번 - 다리 만들기 2 (C++) (0) | 2022.10.12 |
| [ 백준 ] 1956번 - 운동 (C++) (0) | 2022.10.11 |