코딩테스트
[백준] 12920번 : 평범한 배낭2 (JAVA)
1. 문제 분석 이전에 비슷한 배낭문제를 푼 적이 있어 1-0 배낭 문제처럼 풀었다. 그런데 여러 자료구조를 써봤는데도 계속 메모리 초과가 나서 찾아보니 기존의 방법대로 하면 K가 클 경우 계산이 매우 길어지게 된다는 것을 알게 되었다. 새로 찾아낸 방법이 바로 이진 분할이라는 것이였다.M개의 물건을 1부터 2의 거듭제곱 형태로 묶어 새로운 그룹을 만드는 것이였다. 시간복잡도 : O(N log M) 알고리즘 : DP(+ 이진 분할)2. 문제 풀이이 문제의 풀이는 사실 기존의 배낭문제와 다를게 없다. 다만, 중복된 물건을 최대한 간소화 시키는것이 핵심이다.간소화 방법은 다음과 같다.M개의 동일한 물건을 1, 2, 4, ...로 분할 시켜 저장한다. 가치 값도 개수에 맞게 계산하여 서로다른 X개의 물건으로..