[백준 16493번 C/C++] 최대 페이지 수
[백준 16493번 C/C++] 최대 페이지 수
https://www.acmicpc.net/problem/16493
해결전략
Dynamic Programming 다이나믹 프로그래밍, 동적 계획법
배낭
코드
#include <iostream>
#include <vector>
using namespace std;
int n, m;//n 일수, m 챕터의 수
vector<int> day, chapter;
vector<vector<int>> dp;
int main(){
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n >> m;
day.resize(m+1);
chapter.resize(m+1);
for (int i = 1; i <= m; i++)
cin >> day[i] >> chapter[i];
//i개 이하의 챕터를 읽고, j일 이하를 지났을 때 읽을 수 있는 최대 페이지 수
dp.resize(m+1, vector<int>(n+1, 0));
for(int i=1; i<=m; i++){
for(int j=1; j<=n; j++)
{
if (j >= day[i])
dp[i][j] = max(dp[i-1][j], dp[i-1][j-day[i]] + chapter[i]);
else
dp[i][j] = dp[i-1][j];
}
}
//디버깅
//for (int i = 1; i <= m; i++) {
// for (int j = 1; j <= n; j++) {
// cout << dp[i][j] << " ";
// }
// cout << "\n";
//}
cout << dp[m][n];
return 0;
}
'⭐ 코딩테스트 > 백준' 카테고리의 다른 글
[백준 26069번 C/C++] 붙임성 좋은 총총이 (0) | 2023.08.10 |
---|---|
[백준 2178번 C/C++] 미로 탐색 (0) | 2023.08.09 |
[백준 9084번 C/C++] 동전 (0) | 2023.08.03 |
[백준 7579번 C/C++] 앱 (0) | 2023.08.02 |
[백준 12865번 C/C++] 평범한 배낭 (0) | 2023.08.01 |
댓글
이 글 공유하기
다른 글
-
[백준 26069번 C/C++] 붙임성 좋은 총총이
[백준 26069번 C/C++] 붙임성 좋은 총총이
2023.08.10 -
[백준 2178번 C/C++] 미로 탐색
[백준 2178번 C/C++] 미로 탐색
2023.08.09 -
[백준 9084번 C/C++] 동전
[백준 9084번 C/C++] 동전
2023.08.03 -
[백준 7579번 C/C++] 앱
[백준 7579번 C/C++] 앱
2023.08.02