fractional1 [C/C++] 백준 7579: 앱 (Kanpsack-DP) https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 이 문제도 무게(weight)와 가치(value)이 존재하는 전형적인 배낭(Knapsack) 문제이다. 배낭 문제를 해결하는 방법은 용량/비용을 이용하여 backtracking을 하는 방법도 있지만 가장 널리 쓰이고 구현하기 쉬운 Dynamic Programming이 대표적이다. 이 문제 역시 Dynamic Programming을 이용하여 문제를 해결했다. Kanpsack 알고리즘! 배낭 문제를 DP로 .. 2023. 10. 20. 이전 1 다음
