어떤 투자가가 여러 기업들에게 돈을 투자해서 최대의 이익을 얻고자 한다. 단, 투자는 만원 단위로 할 수 있으며 각 기업은 많이 투자할수록 많은 이익을 투자가에게 돌려준다. 돈을 투자하지 않은 경우는 당연히 얻게 되는 이익도 없다. 예를 들어서, 한 투자가가 4만원을 갖고 두 개의 기업들에 각각 만원 단위로 투자했을 경우 얻을 수 있는 이익은 다음과 같다.
투자 액수 (만원)
기업 A
기업 B
1
5
1
2
6
5
3
7
9
4
8
15
위의 경우 만일, 기업 A에 1만원, 기업 B에 3만원을 투자하는 경우 투자가가 얻는 이익은 14만원(5만원+9만원)이다. 4만원을 투자해서 가장 많은 이익을 얻을 경우 기업 B에만 4만원을 투자하는 경우로서 이때의 이익은 15만원이다. 여기서 투자가는 한 기업에 돈을 나누어 투자할 수는 없다.
투자액이 정해져 있고, 기업의 개수와 각 기업에 투자했을 경우에 얻게 되는 이익이 주어졌을 때 가장 많은 이익을 얻을 수 있는 투자방식과 이때의 이익금을 구하는 프로그램을 작성하라.
입력
첫째 줄에 투자 금액 N과 투자 가능한 기업들의 개수 M이 주어진다. (1 ≤ N ≤ 300, 1 ≤ M ≤ 20)
둘째 줄부터 N개의 줄에 투자액수와 각 기업이 투자가에게 주는 이익이 주어진다. 투자 금액은 항상 1보다 크거나 같고, N보다 작거나 같고, 같은 투자 금액이 두 번 이상 주어지는 경우는 없다. 즉, i번 줄에 주어지는 투자 금액은 i-1만원이다.
4 2 1 5 1 2 6 5 3 7 9 4 10 15
출력
첫 줄에 얻을 수 있는 최대 이익을 출력하고, 둘째 줄에는 각 기업에 투자한 액수를 출력한다. 최대 이익은 231보다 작다.
15 0 4
풀이
from sys import stdin
input = stdin.readline
N, M = map(int, input().split())
benefit_info = [[0] * (M+1)] + [list(map(int, input().split())) for _ in range(N)]
DP = [[0] * (M + 1) for _ in range(N + 1)]
investments = [[0] * (M + 1) for _ in range(N + 1)]
def cal_maximum_benefit(price, business):
MAX = benefit_info[price][business]
cur_investment = price
for i in range(price):
temp = DP[price - i][business - 1] + benefit_info[i][business]
if MAX < temp:
MAX = temp
cur_investment = i
return MAX, cur_investment
for i in range(1, N + 1):
for j in range(1, M + 1):
DP[i][j], investments[i][j] = cal_maximum_benefit(i, j)
print(DP[N][M])
result = [0] * M
for business in range(M-1, -1, -1):
result[business] = investments[N][business+1]
N -= investments[N][business+1]
print(*result)
코드 해설
다음은 문제 풀이의 핵심 코드이다.
def cal_maximum_benefit(price, business):
MAX = benefit_info[price][business]
cur_investment = price
for i in range(price):
temp = DP[price - i][business - 1] + benefit_info[i][business]
if MAX < temp:
MAX = temp
cur_investment = i
return MAX, cur_investment
모든 경우의 수를 돌면서, 돈(price)을 1번부터 business번 기업들 중 하나 이상의 기업에 투자하였을 때, 얻을 수 있는 최대 이익(MAX)과 그때 business번 기업에 투자해야할 금액(cur_investment)을 구한다.
코드를 자세히 뜯어보자
MAX = benefit_info[price][business]
cur_investment = price
먼저 최댓값을 모든 돈(price)을 현재 기업에 투자했을 때 얻는 이익으로 초기화한다.
for i in range(price):
temp = DP[price - i][business - 1] + benefit_info[i][business]
if MAX < temp:
MAX = temp
cur_investment = i
그리고 현재기업에 0원부터 price - 1원까지 투자하고, 남은 돈(price - i원)을 지금까지 기업의 앞의 기업들에게 투자를 하였을 때의 이득을 temp에 담는다. 만약 temp가 MAX보다 크다면 MAX를 갱신해주고 이때의 기업(business)에 투자한 금액을 cur_invest에 저장한다.
이를 1원부터 price(전역변수 i)원까지, 1번기업부터 business(전역변수 j)번 기업까지 반복해준다.
for i in range(1, N + 1):
for j in range(1, M + 1):
DP[i][j], investments[i][j] = cal_maximum_benefit(i, j)
DP[i][j]는 i원을 1번 ~ j번 기업들에게 투자하였을 때, 얻을 수 있는 최대 금액이 된다. investments[i][j]는 i원을 1번 ~ j번기업들에게 투자하여 최대 금액을 얻었을 때 j번 기업에 투자해야될 금액이 된다.
다음은 역추적이다.
result = [0] * M
for business in range(M, 0, -1):
result[business - 1] = investments[N][business]
N -= investments[N][business]
모든 기업에 0원을 투자한 것으로 초기화를 한 뒤, 최대 투자 금액인 N부터 시작하여 N원을 business에 투자한것이므로 투자한 금액을 N에서 빼준다. 그러면 business번 기업을 제외한 business - 1번 기업들 까지 중에 남은 N원에서 투자할 금액인 investments[N][business]원을 다시 빼주는 것을 모든 기업에 반복한다.
