Bonjour, tout le monde!

[DP] [BOJ 11052] 카드 구매하기 본문

카테고리 없음

[DP] [BOJ 11052] 카드 구매하기

hygoni 2020. 3. 25. 21:50

 

 

11052번: 카드 구매하기

첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000)

www.acmicpc.net

참고 : 이 문제는 막대 자르기 (rod-cutting 문제와 동일한 문제이다.)

문제

카드가 1개, 2개, 3개, ..., N개가 담긴 카드팩이 있을 때, (카드 팩의 가격은 다를 수 있다.) 카드 N개를 가장 비싸게 살 때의 가격을 구하는 문제

 

해석, 부분 문제, 시간복잡도

문제에 나온 예시를 시각화한 그림. 숫자가 0이 되면 구매가 끝났음을 의미한다.

그림을 그려보면 "카드 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)$만에 답을 구할 수 있다.

 

구현

 

0 Comments
댓글쓰기 폼