[ BOJ ] 2662 : 기업투자 ( GOLD 2 ) / Python

문제

어떤 투자가가 여러 기업들에게 돈을 투자해서 최대의 이익을 얻고자 한다. 단, 투자는 만원 단위로 할 수 있으며 각 기업은 많이 투자할수록 많은 이익을 투자가에게 돌려준다. 돈을 투자하지 않은 경우는 당연히 얻게 되는 이익도 없다. 예를 들어서, 한 투자가가 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만원이다.

출력

첫 줄에 얻을 수 있는 최대 이익을 출력하고, 둘째 줄에는 각 기업에 투자한 액수를 출력한다. 최대 이익은 2^31보다 작다.

풀이 과정

이전 knapsack 문제와는 다른 방식으로 응용해야 했던 문제이다.

dp[m][n] : m 번 기업에 투자했을 때, n 금액까지 투자했을 때의 최대 이익 을 저장했다.

그런데, 1번 기업에 3만원을 투자하고 2번 기업에 1만원을 투자하는게 이득일 수도 있고, 1번 기업에 1만원을 투자하고 2번 기업에 3만원을 투자하는게 이득일 수도 있는 다양한 경우가 존재한다.

 

따라서, 기존 knapsack 과는 다르게 이전 기업에 now_weight 만큼 투자한 것에서, thing 기업에 weight - now_weight 만원 만큼 투자했을 때의 이득이 현재 thing 기업에 weight 만큼 투자한 이득보다 큰 지를 검사했다.

 

한 마디로, 4만원까지 투자했을 때 최대 이득을 알고 싶다면 

이전 기업까지 0만원 투자하고 지금 기업에 4만원 투자한 이득,

이전 기업까지 1만원 투자하고 지금 기업에 3만원 투자한 이득,

이전 기업까지 2만원 투자하고 지금 기업에 2만원 투자한 이득,

이전 기업까지 3만원 투자하고 지금 기업에 1만원 투자한 이득,

이전 기업까지 4만원 투자하고 지금 기업에 0만원 투자한 이득을 모두 검토했다고 보면 된다. ( 제한이 적어서 쉽게 넘어갈 수 있었다. )

 

최대 이득을 저장함과 동시에, 특정 기업에 얼마나 투자했는지를 저장하는 배열도 함께 테이블에 구성했다.

만약 최대 이득을 갱신했다면, 이전 기업에 투자한 정보에 현재 기업에 투자한 금액 정보를 추가해서 투자 정보를 쌓았다.

import sys
input = sys.stdin.readline

n, m = map(int, input().rstrip().split())
arr = [[0 for _ in range(m)]]
for _ in range(n):
    tmp = list(map(int, input().rstrip().split()))
    arr.append(tmp[1:])

dp = [[[0, [0 for _ in range(m+1)]] for _ in range(n+1)] for _ in range(m+1)]
# dp[m][n] : m 번까지 투자했을 때 n 금액까지 투자했을 때 최대 이익

for weight in range(1, n+1):
    for thing in range(1, m+1):
        for now_weight in range(weight+1):
            if dp[thing][weight][0] < dp[thing-1][now_weight][0] + arr[weight - now_weight][thing-1]:
                dp[thing][weight][0] = dp[thing-1][now_weight][0] + arr[weight - now_weight][thing-1]

                dp[thing][weight][1] = list(dp[thing-1][now_weight][1])
                dp[thing][weight][1][thing] = weight - now_weight

max_value = 0
max_pos = []
for i in range(m+1):
    for j in range(n+1):
        if max_value < dp[i][j][0]:
            max_value = dp[i][j][0]
            max_pos = [i, j]

print(dp[max_pos[0]][max_pos[1]][0])
print(' '.join(map(str, dp[max_pos[0]][max_pos[1]][1][1:])))