문제 https://www.acmicpc.net/problem/12920 12920번: 평범한 배낭 2 첫 번째 줄에 N, M (1 ≤ N ≤ 100, 1 ≤ M ≤ 10,000) 이 빈칸을 구분으로 주어진다. N은 민호의 집에 있는 물건의 종류의 수이고 M은 민호가 들 수 있는 가방의 최대 무게다. 두 번째 줄부터 N개의 줄에 www.acmicpc.net 풀이 solved.ac 난이도: Platium5 [백준] 평범한 배낭(12865)의 다음 단계 문제로 같은 물건이 여러 개 있는 경우이다. 이 문제를 일반적인 배낭(Knapsack) 문제와 동일하게 해결하려 시간 복잡도가 O(N* K *M)이기 때문에 시간 초과가 발생한다. 따라서 다음과 같은 최적화가 필요하다. 물건의 개수를 2의 제곱수의 합으로 분..