<문제 링크>
백준 11052번 카드 구매하기
1~N까지의 개수만큼 카드가 들어있는 카드팩이 있고, 각 카드팩마다 가격이 정해져 있다. N개의 카드를 얻기 위해 카드팩을 구매하는 여러가지 경우들 중, 가장 비싼 경우의 가격을 구해야 한다. (가격의 최대값)
-> 입력 : N, 각 카드팩의 가격
-> 출력 : 가격의 최대값
ex0)
-> N : 4
-> 가격
(P(N) : N개의 카드가 들어있는 카드팩)
카드팩 | 가격 |
---|---|
P(1) (카드1장) | 1 |
P(2) (카드2장) | 5 |
P(3) (카드3장) | 6 |
P(4) (카드4장) | 7 |
-> 4장의 카드를 얻기 위해 카드팩을 구매하는 여러가지 경우들 중, 가장 비싼 가격에 구매할 수 있는 경우는 P(2)를 2개 구매하는 것이다.
따라서 출력은 5 * 2 = 10이 된다.
처음에는 카드 1장의 값이 가장 큰 카드팩을 최대한 많이 사면 되는줄 알았다.
그렇게 1시간을 날릴 수 있었다.
본 문제는 DP 개념을 적용해서 풀 수 있는 문제인데, 규칙을 파악할 때 다음과 같이 생각해 볼 수 있다.
위 문제 요약의 예시 ex0)으로 생각해보자.
입력 : N = 4, 1 5 6 7
(D(N) : 본 문제의 정답 / P(N) : N개의 카드가 들어있는 카드팩의 가격)
- N = 4일 때, 고려해야 하는 카드팩의 경우의 수는 굉장히 많다. (P(1) 4개, P(1) 2개 P(2) 1개, ...)
-> 이걸 하나하나 다 생각하기에는 N이 너무 크다.
- N을 줄여서 생각해 보고, N이 늘어날 수록 일관된 규칙을 찾는다.
-> D(1) : P(1)이 최대값 : 1
-> D(2) : "(P(1)+P(1)) 혹은 P(2)" 중 큰게 최대값, P(2)가 더 크다 : 5
-> D(3) : "(P(1)+P(1)+P(1)) 혹은 (P(1)+P(2)) 혹은 P(3)" 중 큰게 최대값인데, P(1) 3개는 D(2)에서 걸러진다. 결국 "P(1)+P(2) vs P(3)"인데 둘은 같다 : 6
-> ...
- 위 2번의 D(3)을 보면, 결국 D(1) + D(2)와 P(3)을 비교하고 있는 것을 파악할 수 있다.
-> "카드 1장 살 때, 2장 살 때 제일 비싸게 고른 경우의 가격"과 "P(3)"을 비교하면 된다.
이를 그대로 N을 늘려나가 보면, 아래와 같이 점화식을 구할 수 있게 된다.
D(N) = max(P(N), D(1) + D(N-1), D(2) + D(N-2), ... D(N//2) + D(N-N//2))
위 점화식은 아래와 같이 동작한다.
아래는 D(7)을 구하는 과정이다.
(D(1)~D(6)은 예시로 아무 숫자나 넣은 것이다.)
결국 D(N)을 구하려면 D(1)~D(N-1)까지 모두 알아야 하는데,
각 연산의 결과를 저장해 두지 않고 그때 그때 구하게 되면 얼마나 걸릴지 감도 안잡힌다.
따라서 어차피 D(1)부터 D(N-1)까지 다 알아야 하니, D(1)부터 위로 차근 차근 쌓아가듯이 구하면 된다.
<필자가 작성한 코드>
(위에 적힌 규칙을 직관적으로 보기 위해 구현한 코드이다. 마지막에 더 간단히 구현된 코드가 있다.)
N = int(input())
cards = list(map(int, input().split()))
answer = 0
DN = [0] * N
DN[0] = cards[0]
for i in range(1, len(cards)):
start = -1
end = i
newOne = 0
while start < end:
start += 1
end -= 1
if start == end:
if newOne < (DN[start] * 2):
newOne = DN[start] * 2
else:
if newOne < (DN[start] + DN[end]):
newOne = DN[start] + DN[end]
if newOne < cards[i]:
DN[i] = cards[i]
answer = cards[i]
else:
DN[i] = newOne
answer = newOne
print(answer)
DN 리스트에 1~N까지의 D(N) 결과를 저장한다.
저장하는 과정에서
newOne 변수에 D(1)~D(N-1)까지 N을 만들 수 있는 모든 경우 중 최대 값을 저장하고,
그 최대값과 P(N) 중 더 큰 값을 선택한다.
<더 간단한 코드>
N = int(input())
cards = [0]
cards += list(map(int, input().split()))
DN = [0] * (N+1)
DN[1] = cards[1]
DN[2] = max(cards[2], cards[1]*2)
for i in range(3, N+1):
DN[i] = cards[i]
for j in range(1, i//2 + 1):
DN[i] = max(DN[i], DN[j] + DN[i-j])
print(DN[N])
DP는 언제 풀어도 항상 어려운 것 같다ㅠ