rainyCode rainyCode

#골드5 백준 12865번 문제는 정말 유명한 알고리즘인 knapsack 알고리즘의 대표문제이다. knapsack 알고리즘은 쪼갤 수 있냐 없냐에 따라 두 가지로 나뉘는데 만약 쪼갤 수 없다면, brute force와 dynamic programming으로 풀 수 있다. 그러나 brute force 방법은 시간복잡도가 O(2^n)만큼 잡아먹어서 n이 크다면 극악의 시간복잡도이다. 그래서 웬만한 ps에는 쓰이지 않을 것이다. 반면에 dp는 중첩 for문으로 이차원 배열을 사용하기 때문에 O(n^2)으로 쓸만하다. 추가적으로 만약 쪼갤 수 있는 knapsack 문제이면 greedy하게 해결도 가능하다. 이 방법은 다른 포스팅에서 다뤄보겠다. 문제 링크 https://www.acmicpc.net/problem..