문제 링크입니다: https://www.acmicpc.net/problem/1535
전형적인 Knapsack DP 문제였습니다.
세준이의 체력이 0이어도 기쁨을 못 느낀다는 것이 핵심이었습니다.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
using namespace std; | |
const int MAX = 100 + 1; | |
int N; | |
int cache[MAX]; | |
pair<int, int> arr[MAX]; | |
int main(void) | |
{ | |
ios_base::sync_with_stdio(0); | |
cin.tie(0); | |
cin >> N; | |
for (int i = 0; i < N; i++) | |
{ | |
cin >> arr[i].first; | |
} | |
for (int i = 0; i < N; i++) | |
{ | |
cin >> arr[i].second; | |
} | |
for (int i = 0; i < N; i++) | |
{ | |
for (int j = 100; j > arr[i].first; j--) | |
{ | |
cache[j] = max(cache[j], arr[i].second + cache[j - arr[i].first]); | |
} | |
} | |
cout << cache[100] << "\n"; | |
return 0; | |
} |

개발환경:Visual Studio 2022
지적, 조언, 질문 환영입니다! 댓글 남겨주세요~
반응형
'알고리즘 > BOJ' 카테고리의 다른 글
백준 1344번 축구 (0) | 2024.05.08 |
---|---|
백준 17837번 새로운 게임 2 (0) | 2024.05.07 |
백준 1513번 경로 찾기 (0) | 2024.05.06 |
벡즌 12865번 평범한 배낭 (0) | 2024.05.06 |
백준 12852번 1로 만들기 2 (0) | 2024.05.06 |