문제https://www.acmicpc.net/problem/9084문제 이해N가지 동전으로 금액 M을 만드는 모든 방법의 수를 구한다.문제 풀이🔍 접근이 문제는 대표적인 Unbounded Knapsack 문제다.아래의 배낭 문제에서 각 물건을 1번만 선택할 수 있었던 점과 다르게, 같은 동전을 여러번 넣을 수 있다. [BOJ][C++] 백준 12865번: 평범한 배낭문제https://www.acmicpc.net/problem/12865 문제 이해최대 무게(K)가 정해진 배낭에 물건을 넣는다. N개의 물건에는 각각 무게(W)와 가치(V)가 있다.배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 구한다.y-e-99.tistory.com 💡 Dynamic Programming목표 금액을 인덱스로, 목표 금..

문제https://www.acmicpc.net/problem/12865 문제 이해최대 무게(K)가 정해진 배낭에 물건을 넣는다. N개의 물건에는 각각 무게(W)와 가치(V)가 있다.배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 구한다. 문제 풀이❔ 브루트포스물건의 가능한 모든 조합을 구한다.N개의 물건에 대해 넣을지 말지를 모두 시도한다. O(2^N)이고, N ≤ 100이므로 제한시간 초과 ❔ 백트래킹물건의 가능한 모든 조합을 구하면서 최대 무게를 넘어가는 경우를 가지치기로 줄인다.최악의 경우로, 모든 조합이 최대 무게를 넘어가지 않으면, 브루트포스와 같아진다. 💡 Dynamic ProgrammingDP를 통해 이전 결과를 저장해서 중복 계산을 피한다.'배낭의 최대 무게'를 인덱스로, 가치합의 최댓값..