https://www.acmicpc.net/problem/14728
14728번: 벼락치기
ChAOS(Chung-ang Algorithm Organization and Study) 회장이 되어 일이 많아진 준석이는 시험기간에도 일 때문에 공부를 하지 못하다가 시험 전 날이 되어버리고 말았다. 다행히도 친절하신 교수님께서 아래와
www.acmicpc.net
[난이도] Gold5
[유형] DP
[풀이]
전형적인 배낭문제입니다.
#include <cstdio>
#include <algorithm>
using namespace std;
int N,T,dp[10001];
pair<int,int> p[100];
int main(){
scanf("%d%d",&N,&T);
for(int i=0;i<N;i++) scanf("%d%d",&p[i].first,&p[i].second);
for(int i=0;i<N;i++){
for(int j=T;j>=0;j--){
if(j-p[i].first>=0) dp[j] = max(dp[j],dp[j-p[i].first]+p[i].second);
}
}
int ans=0;
for(int i=1;i<=T;i++) ans=max(ans,dp[i]);
printf("%d",ans);
}
https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/14728.cpp
'Problem-Solving > BOJ' 카테고리의 다른 글
| [BOJ/백준][Gold5] 15591 : MooTube (Silver) (C++) (0) | 2022.01.23 |
|---|---|
| [BOJ/백준][Gold5] 14395 : 4연산 (C++) (0) | 2022.01.23 |
| [BOJ/백준][Gold5] 2591 : 숫자카드 (C++) (0) | 2022.01.23 |
| [BOJ/백준][Gold5] 1041 : 주사위 (C++) (0) | 2022.01.23 |
| [BOJ/백준][Gold5] 6987 : 월드컵 (C++) (0) | 2022.01.23 |