[파이썬/python] 백준 - 2662 기업투자

문제

https://www.acmicpc.net/problem/2662

---

문제 설명

1. 여러 기업에게 돈을 투자해서 최대의 이익을 얻고자 한다.
   1. 투자는 만원 단위로  가능하다.
   2. 각 기업에게 많은 돈을 투자할수록 많은 이익을 돌려준다.
2. 투자액이 정해져 있고, 기업의 개수와 금액 별 이익이 주어진다.
3. 가장 많은 이익을 얻을 수 있는 투자 방식과 이익금을 구한다.

 

---

풀이

문제를 보자마자 다이나믹 프로그래밍이 생각났지만, 어떻게 구현을 해야할 지 잘 떠오르지 않았다.

문제를 다시 읽어보니, 각 기업과, 기업 별 코스트로 나뉘어지는 것을 알고 보니, 배낭 문제와 유사하다고 생각했다.

 

기존 배낭 문제는 아이템과 코스트로 다이나믹 프로그래밍을 진행하는데, 이 문제는 하나의 아이템(기업)에 4가지의 코스트가 존재했다.

따라서 기존 배낭 알고리즘을 응용하여 최대 이익금을 구한 후, 3차원 DP 배열을 통해 최대값이 갱신 될 시점에 현재 몇 만원을 투자했는지 기록하여, 역추적을 통해 투자 방식을 탐색했다.

1. 3차원 DP배열을 만들고, 시작 지점을 초기화한다.
2. 기존 배낭 알고리즘과 똑같이 구현하되 1만원부터 N만원까지 모두 탐색을 돌면서 최댓값을 갱신한다.
   1. 이 때 최댓값이 갱신된다면 해당 위치에 얼마를 투자했는지 기록한다.
3. 최종적으로 마지막 기업부터 순차적으로 탐색하며, 각 기업에 얼마를 투자했는지 구한다.

---

코드

import sys
input = sys.stdin.readline

n,m = map(int,input().split())

money = [[0 for _ in range(n+1)] for _ in range(m)]

for i in range(n):
    c = list(map(int,input().split()))
    for j in range(m):
        money[j][c[0]] = c[j+1]
dp = [[[0,0,0] for _ in range(n+1)] for _ in range(m)]
dp[0][0][1] = -1
for i in range(1,n+1):
    dp[0][i] = [money[0][i],-1,i]

for i in range(1,m):
    for cost in range(n+1):
        dp[i][cost] = [dp[i-1][cost][0], i-1,0]
        for curr_cost in range(cost+1):

            if dp[i-1][cost][0] < dp[i-1][cost-curr_cost][0] + money[i][curr_cost]:
                if dp[i][cost][0] >= dp[i-1][cost-curr_cost][0] + money[i][curr_cost]:
                    continue
                dp[i][cost][0] = dp[i-1][cost-curr_cost][0] + money[i][curr_cost]
                dp[i][cost][2] = curr_cost

v = m-1
c = n
res = [dp[v][c][2]]
while v > 0:
    c -= dp[v][c][2]
    v -= 1
    res.append(dp[v][c][2])

print(dp[m-1][n][0])
print(*list(reversed(res)))

---

시간복잡도

• 배낭 DP알고리즘의 시간복잡도는 물건의 수 * 코스트이다. 즉 최대 기업의 수 $M = 20$, 최대 투자 금액 $N = 300$이므로
  M*N이다. 하지만 추가로 각 기업 별 Cost를 전부 탐색하기 때문에, $M*N*(N+1)/2$의 시간이 소요된다.
• 따라서 약 $O(20*300*150) = O(10**6)$의 시간복잡도가 소요된다.