[BOJ] 백준 2662번 기업투자 (Python)

BOJ: Q2662 - 기업투자 [ 골드 3 ]

문제

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

출력

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

예제

입력 1

4 2
1 5 1
2 6 5
3 7 9
4 10 15

출력 1

15
0 4

입력 2

6 3
1 5 1 3
2 6 5 5
3 7 9 7
4 10 15 10
5 13 21 14
6 16 27 19

출력 2

27
0 6 0

입력 3

4 3
1 5 1 2
2 6 5 4
3 7 9 11
4 8 15 12

출력 3

16
1 0 3

풀이

일단 냅색 알고리즘을 알아야 한다. 한정된 무게를 버틸 수 있는 가방과 여러개의 물건들이 있고, 물건들을 각각 무게와 가치가 매겨져 있다. 냅색 알고리즘은 가방에 물건들을 담는데, 가방 안에 담은 물건들의 가치가 가장 높게 물건을 담는 알고리즘을 말한다.
이 문제도 한정만 투자금을 주어진 기업들에게 투자하여 최대한 많은 이익을 얻는 것이 목적이므로, 냅색 알고리즘을 사용하여 풀 수 있다.

예제 입력 3을 예로 들어 설명해보려 한다. 주어진 예산은 4만원이고, 기업은 3곳이다. 투자 액수 당 이익은 아래 표와 같다. 이 표를 'Arr'라고 칭하겠다.

• Arr

투자 액수 (만원)	기업 A	기업 B	기업 C
1	5	1	2
2	6	5	4
3	7	9	11
4	8	15	12

1만원부터 4만원까지 투자했을 때의 표를 만드는데, 투자금일 1만원일 때 A기업까지 고려했을 경우 최대 이익, B 기업까지 고려했을 경우 최대 이익, .. 이런식으로 표현되는 표를 만들 것이고 해당 표를 Table이라 칭하겠다.
일단 1만원만 투자했을 경우, 아래와 같이 된다.

• 1만원 투자 시,

투자 액수 (만원)	기업 A	기업 B	기업 C
1	5	5	5

위 표를 다시 해석하자면,
Table[1][1]은 1만원을 투자하는데, 기업 A만 고려했을 때 Arr을 보면 Arr[1][1] == 5이므로 돌려 받을 수 있는 이익이 5이다. 따라서 Table[1][1]에 5가 들어간다.
Table[1][2]은 1만원을 투자하는데, 기업 A부터 기업 B까지 고려했을 때 Arr을 보면 Arr[1][1]이 5, Arr[1][2]이 1이다. 따라서 Table[1][2]에 둘 중 더 큰 수인 5가 들어간다.
Table[1][3]은 1만원을 투자하는데, 기업 A부터 기업 C까지 고려했을 때 Arr을 보면 Arr[1][1]이 5, Arr[1][2]이 1, Arr[1][3]이 2이다. 따라서 Table[1][3]에 5가 들어간다.

여기서, Table[1][3]은 여러 수를 동시에 비교했다. 하지만 Table[1][2]는 이미 Arr[1][1]과 Arr[1][2]를 비교한 것이기 때문에, Table[1][3]은 Table[1][2]와 Arr[1][3]만 비교하면 된다.
이런 식으로 하면 Arr[1][2] 또한 Table[1][1]과 Arr[1][2]만 비교하면 된다.

• 2만원 투자 시,

투자 액수 (만원)	기업 A	기업 B	기업 C
1	5	5	5
2	6	6	7

위 표에서 3번째 줄인 투자 액수 2만원 인 경우를 해석하자면,
Table[2][1]은 2만원을 투자할 때, 기업 A만 고려했을 경우의 최대 이익이다. 2만원을 모두 기업 A에게 투자한 것이므로, Table[2][1]은 6이 된다.

Table[2][2]는 2만원을 투자할 때, 기업 A부터 기업 B까지 고려했을 경우의 최대 이익이다. 2만원을 모두 기업 A에 투자한 경우 또는 기업 A에 1만원, 기업 B에 1만원 투자하면 6만원의 이익이 난다. 2만원을 모두 기업 B에 투자한 경우, 이익은 5만원이므로 이 때는 제외한다. 따라서 Table[2][2]는 6이다.

Table[2][3]은 2만원을 투자할 때, 기업 A부터 기업 B까지 고려했을 경우의 최대 이익이다. Table[2][2]와 Table[1][2] + Arr[1][3] (기업 A 1만원 + 기업 C 1만원), Arr[2][3] (2만원 모두 기업 C에 투자) 세 경우를 비교해 볼 수 있다.

Table[2][2] == 6
Table[1][2] + Arr[1][3] == 5 + 2 == 7
Talbe[2][3] == 4

따라서 Table[2][3]은 7이 된다.

• 3만원 투자 시,

투자 액수 (만원)	기업 A	기업 B	기업 C
1	5	5	5
2	6	6	7
3	7	10	11

방법은 위와 동일하다.
Table[3][1]은 Arr[3][1]과 동일하다. 따라서 Table[3][1]은 7이다.

Table[3][2]는 Table[3][1]과 Arr[3][2], Table[1][1] + Arr[2][2] (기업 A까지 1만원 투자 최댓값 + 기업 B만 2만원 투자), Table[1][2] + Arr[1][2](기업 A까지 2만원 투자 최댓값 + 기업 B만 1만원 투자)을 비교하여 가장 큰 숫자를 넣는다.

Table[3][1] == 7
Arr[3][2] == 9
Table[1][1] + Arr[2][2] == 5 + 5 == 10
Table[2][1] + Arr[1][2] == 6 + 1 == 7

따라서 Table[3][2]는 10이다.

Table[3][3]는 Table[3][2]와 Arr[3][3], Table[1][2] + Arr[2][3] (기업 B까지 1만원 투자 최댓값 + 기업 C만 2만원 투자), Table[2][2] + Arr[1][3](기업 B까지 2만원 투자 최댓값 + 기업 C만 1만원 투자)을 비교하여 가장 큰 숫자를 넣는다.

Table[3][2] == 10
Arr[3][3] == 11
Table[1][2] + Arr[2][3] == 5 + 4 == 9
Table[2][2] + Arr[1][3] == 6 + 2 == 8

따라서 Table[3][3]는 11이다.

위와 같은 방법을 사용하면, 투자 가능 금액이 4만원일 경우는 아래와 같다.

• 4만원 투자 시,

---|---|---|---
1| 5| 5 |5
2| 6| 6 |7
3| 7| 10 | 11
4| 8 | 15| 16

따라서 가장 수익금이 큰 경우는 16만원이 된다.
수익금이 가장 큰 경우의 투자 방법은 따로 테이블을 만들고, 그곳에 저장하면 된다.

최종적인 코드는 아래와 같다.

N, M = map(int, input().split())		# 금액, 기업 수 입력
byInvestment = [[0 for _ in range(M + 1)]]	# 기업 투자금액별 수익금 저장 리스트.

for _ in range(N):				# 기업별 수익금 데이터 추가
    byInvestment.append(list(map(int, input().split())))

# 최대 이익 계산할 테이블
table = [[0 for _ in range(M + 1)] for _ in range(N + 1)]
# 최대 이익시 투자할 기업을 추적할 테이블
pos = [[[0 for _ in range(M+1)] for _ in range(M + 1)] for _ in range(N+1)]

for i in range(1, N + 1):			# 행, 투자금
    for j in range(1, M + 1):			# 열, 기업
        # table[i][j]에 이전기업까지 고려했을 때의 최댓값과 현재 기업에 모든 돈을 투자한 경우 중 최댓값 대입
        table[i][j] = max(table[i][j-1], byInvestment[i][j])
        if table[i][j] == byInvestment[i][j]:	# 만약 현재 기업에 모두 투자하는 것이 이익이 더 크다면
            pos[i][j][j] = i			# 방법 추적
        else:					# 이전기업까지 고려한 경우가 더 크다면
            pos[i][j] = pos[i][j-1].copy()	# 이전기업까지 고려한 것을 복사
            
        # 현재 기업 소량 분산투자하는 경우 (이전 기업 투자 최댓값 + 현재 기업 투자)
        for k in range(1, i+1):
            # 만약 현재 table[i][j] 값보다 이전 기업들 + 현재 기업 투자하는 것이 더 크다면
            if table[i][j] < table[k][j-1] + byInvestment[i-k][j]:
                # 값 대입
                table[i][j] = table[k][j-1] + byInvestment[i-k][j]
                pos[i][j] = pos[k][j-1].copy()	# 이전 방법 복사
                pos[i][j][j] = i-k		# 현재 기업 투자금 추가
                
# 출력
print(table[-1][-1])
print(*pos[-1][-1][1:])

실제 코드에서는 Table과 기업별 수입 표의 맨 앞에 0으로만 이루어진 행, 행마다 맨 앞 원소 0을 추가하여 코드를 더 쉽게 작성할 수 있도록 한다.