알고리즘/BOJ

백준 1535번 안녕

꾸준함. 2024. 5. 7. 00:04

문제 링크입니다: https://www.acmicpc.net/problem/1535

 

전형적인 Knapsack DP 문제였습니다.

세준이의 체력이 0이어도 기쁨을 못 느낀다는 것이 핵심이었습니다.

 

#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;
}
view raw .cpp hosted with ❤ by GitHub

 

개발환경: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