문제 : https://www.acmicpc.net/problem/2629 풀이 배낭문제(knapsack problem)를 응용한 문제이다.(12865번 문제 참고) 점화식을 아래처럼 설계한다. dpi=i번째 추를 넣을경우, 안넣을경우, 반대편에 넣을경우 만들 수 있는 구슬의무게 즉, i-1번째 무게가 weight이고 i번째 추의 무게가 j인 경우 dpi dpi dpi 위의 3가지는 구슬의 무게로 가능한 가짓 수 이다. 이때, weight-j는 0보다 커야하며(무게가 음수일 수는 없다) 중복되는경우는 없애는 것이 좋다(재귀함수 반복 줄이기) dp배열이 완성된 경우 해당 구슬의 무게에 해당하는 dp배열을 순회하면서 True가 있는지 조회. 아래의 방법은 2차원 dp배열 대신 set을 이용한 방법이다. 위와 같은 방법으로 이루어지지만, set을 이용해 훨씬 간결하게 작성된 방법.

문제 : https://www.acmicpc.net/problem/11066 풀이 dp를 이용해 해결하는 문제이다. 최소비용은 책이 n권있다고 가정할 때, 매번 합칠때마다 비용이 중첩되어 발생한다 즉, 1~n권까지의 각각의 책의 비용+매번 합칠때 드는 비용 = 최소비용이다. dpi=i에서 j까지의 최소비용으로 점화식을 계산한다. 최소비용의 계산방법은 아래와 같다 **편한 계산을 위해 idx는 1부터 시작하게 임의로 설정했습니다. 주어진 크기가 li=[0,40,30,30,50,20]인 예시로 확인해본다. 책을 합치는 구간이 1일때, 먼저, dpi=는 존재하지않는다.(합치지 않아 비용이 발생하지 않으므로) ![](https://velog.velcdn.com/images/www-jong/p