출처: 백준 온라인 저지
https://www.acmicpc.net/problem/11052
처음 잘못된 접근
from sys import stdin
n = int(stdin.readline())
prices = [int(x) for x in stdin.readline().split()]
price_per_one = []
for i, price in enumerate(prices, 1):
price_per_one.append((i, price / i))
price_per_one.sort(key=lambda x: x[1], reverse=True)
(어쩌고저쩌고)
카드 구매 가격을 장당 가격 순으로 정렬한 뒤, 장당 가격이 비싼 것부터 점화식을 활용해서 풀이하고자 하였다. 장당 가격이 가장 비싼 것을 포함하는 경우와 그렇지 않은 경우로 나누어 점화식을 만들었다. 하지만 이 접근은 2가지 문제가 있었다.
1) 장당 가격이 비싼 것부터 채운다고 해서 전체 금액이 가장 비싸지지 않는다. 다시 말해서, 그리디 알고리즘이 적용되지 않는다. 동적 프로그래밍 문제를 그리디 알고리즘으로 잘못 접근했다.
2) 이 점화식은 너무 많은 Recursion을 야기한다.
정답률이 60% 이상인데도 풀지 못해서 포기하고, 다른 사람들의 풀이를 찾아보았다.
맞는 풀이
from sys import stdin
n = int(stdin.readline())
prices = [0] + [int(x) for x in stdin.readline().split()]
# max_prices = prices라고 하면, 복사가 아니라 참조가 되어
# 한 곳을 변경하면 다른 곳도 똑같이 변경된다.
# (이 코드에서는 참조로 해도 이상은 없음.)
max_prices = prices[:]
for i in range(2, n + 1):
for j in range(1, i // 2 + 1):
if max_prices[i] < max_prices[i - j] + max_prices[j]:
max_prices[i] = max_prices[i - j] + max_prices[j]
print(max_prices[n])카드 n장을 한번에 구매하는 가격이 price(n)이고,
카드 n장을 구매할 때의 최대 금액을 max_price(n)이라고 하자.
그렇다면 max_price(n)은
price(n)
max_price(n - 1) + max_price(1)
max_price(n - 2) + max_price(2)
...
max_price(n - k) + max_price(k) 중 가장 큰 값과 같다.
사실 점화식 자체는 간단한데, 장당 가격이라는 요소에 집착하느라 정작 간단한 풀이를 보지 못한 것 같다. 동적 프로그래밍 문제를 풀 때는 우선 기본 점화 관계를 밝힌 뒤에, 보다 효율성을 높일 수 있는 방안을 생각하도록 해야겠다.
(위 코드에서 for j in range(1, i // 2 + 1): 부분에서 i를 n이라고 한 걸 못 찾아서 또 15분을 헤맸다. 사소한 실수를 줄이도록 꼼꼼하게 풀기)
