11052번: 카드 구매하기
첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000)
www.acmicpc.net
참고 : 이 문제는 막대 자르기 (rod-cutting 문제와 동일한 문제이다.)
문제
카드가 1개, 2개, 3개, ..., N개가 담긴 카드팩이 있을 때, (카드 팩의 가격은 다를 수 있다.) 카드 N개를 가장 비싸게 살 때의 가격을 구하는 문제
해석, 부분 문제, 시간복잡도
그림을 그려보면 "카드 2개를 사는 최대 가격", "카드 1개를 사는 최대 가격" 등의 부분 문제가 중복됨을 알 수 있다. 이를 좀 더 일반화해보자.
N개의 카드를 사는 최대 가격은 (1 <= i <= N) 일 때,
(N개의 카드를 사는 최대 가격) = (카드 i가 들어있는 카드팩 가격) + (N-i개의 카드를 사는 최대 가격)
으로 분해할 수 있다. 그렇다면 Bottom-Up Method를 이용해서 1, 2, 3, ..., K-1에 대한 정답을 미리 구해놓는다면, $O(N)$만에 K에 대한 정답을 구할 수 있게 되어 최적화를 할 수 있다. 그럼 K = 1, 2, 3, ..., N에 대해서 N개의 문제를 $O(N)$만에 해결할 수 있으므로 우리가 원하는 "N개의 카드를 사는 최대 가격"은 $O(N^2)$만에 답을 구할 수 있다.
구현
댓글