[DP] 기업투자 문제 풀이

백준 기업투자 문제 : https://www.acmicpc.net/problem/2662

문제 요약

- 일정금액을 기업들에게 돈을 투자해서 최대 이익을 얻고자한다.

- 투자액이 정해져 있고 기업의 개수와 기업에 투자할 이익이 주어질 때, 가장 많은 이익을 얻을 수 있는 투자방식과 이익금을 구하기

위의 경우 최대 이익을 얻는 경우는 B기업에만 4만원을 투자하는 경우 15만원입니다.

우선 문제의 기본 입력을 받고 필요한 함수를 구현합니다.

#include<iostream>
 
using namespace std;
 
int arr[301][21];
int DT[301][21];
 
int M, C;
 
int MAX(int a, int b)
{
    return (a > b) ? a : b;
}
 
int main()
{
    int testcase;
    cin >> testcase;
 
    for (int tc = 0; tc < testcase; tc++)
    {
        cin >> M >> C;
        for (int i = 1; i <= M; i++)
            for (int j = 0; j<= C; j++)
                cin >> arr[i][j];
 
    }
    return 0;
}
 

이 문제를 처음 풀때는 풀 방법이 전혀 생각이 나지 않았었다가  0/1 Knapsack 문제를 먼저 풀어보고 어떻게 접근해야 될지 감이 잡혔습니다.

Knapsack 문제를 아직 안풀은 사람은 먼저 풀어보고 기업투자를 풀어보는게 좋습니다.

 ->0/1 Knapsack

이 문제 역시 작은 문제를 생각해보고, 작은 문제를 푼값을 통해 큰 문제를 풀어보면 됩니다.

테이블을 하나 그린 후 C기업까지 있다고 생각하고 아래와 같이 테이블을 그립니다.

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

그리고 각 기업에 일정금액을 투자할 수 있을 때 얻을 수 있는 이익을 구하는 테이블,

테이블의 값은 TABLE[i][j] = i까지 금액으로 기업 j까지 투자할 때 얻을 수 있는 최대이익(i=투자금액,j=기업)이라고 생각합니다.

그렇다면 금액을 1만원 투자할때 얻을 수 있는 최대 이익은 아래와 같습니다.

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

 - TABLE[1][1] = 1만원으로 기업A까지 투자할 때 얻는 최대 이익 = 5만원(기업 A투자)
 - TABLE[1][2] = 1만원으로 기업A~B까지 투자할 때 얻는 최대 이익 = 5만원(기업 A투자)
 - TABLE[1][3] = 1만원으로 기업A~C까지 투자할 때 얻는 최대 이익 = 5만원(기업 A투자)

금액을 2로 늘려보자.

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

 - TABLE[2][1] = 2만원으로 기업 A까지 투자할 때얻는 최대 이익 = 6만원(기업 A투자)
 - TABLE[2][2] = 2만원으로 기업 A~B까지 투자할 때 얻는 최대 이익 = 6만원(기업 A투자 or 기업 A 1만원 + 기업B 1만원 투자)
 - TABLE[2][3] = 2만원으로 기업 A~C까지 투자할 때 얻는 최대 이익 = 7만원(기업 B 1만원 + 기업C 1만원)
    -> 이때의 모든 경우는
         1) 기업 B까지 2만원 투자할 떄 최대금액 -> 6만원 (TABLE[2][2])
         2) 2만원을 기업 C에 투자 ->4만원 (arr[2][3])
         3) 기업 B까지 1만원 투자할 때 최대금액 5만원 + 기업 C 1만원투자 2만원 -> 7만원 (TABLE[1][2] + arr[2][3])
     위 세가지 경우중 최댓값 7만원

다시 금액을 3만원까지 늘려보자.

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

 - TABLE[3][1] = 3만원으로 기업 A까지 투자할 때 얻는 최대 이익 -> 7만원 (기업 A 투자)
 - TABLE[3][2] = 3만원으로 기업 A~B까지 투자할 때 얻는 최대 이익 -> 10만원 (기업 A 1만원 + 기업 B 2만원)
 - TABLE[3][3] = 3만원으로 기업 A~C까지 투자할 때 얻는 최대 이익 -> 11만원(기업 C 3만원)

1만원만 더 늘려보자.

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

TABLE[4][3]를 봤을 때..

 1) 경우의 수는 아래와 같습니다.

  - 4만원으로 기업C에 몽땅 투자 -> 12만원 (arr[4][3])
  - 기업 B까지 4만원을 투자할 때 얻을 수 있는 최대금액(C를제외) ->15만원(TABLE[4][2])

위 두가지 중 최댓값 : DT[4][3] = MAX(arr[4][3], TABLE[4][2])

 2) 또한, 아래 경우의 수중 최댓값

  - 기업 B까지 1만원 투자할 때 최대 금액 + 기업 C 3만원투자 -> 5만원 + 11만원 = 16만원 (TABLE[1][2] + arr[3][3])
  - 기업 B까지 2만원 투자할 때 최대 금액 + 기업 C 2만원투자 -> 6만원 + 4만원 = 11만원 (TABLE[2][2] + arr[2][3])
  - 기업 B까지 3만원 투자할 때 최대 금액 + 기업 C 1만원투자 -> 10만원 + 2만원 = 12만원 (TABLE[3][2] + arr[1][3])

코드로 작성하면 아래와 같습니다.

int val = 0;
for (int k = 1; k <4; k++)
    val = MAX(val, TABLE[k][2] + arr[i - k][3]);

1)의 값과 2)의 값 중 최댓값을 넣어 주면됩니다.

TABLE[4][3] = MAX(TABLE[4][3], val);

이제 위의 구한 식을 일반화 하여 DT을 구하는 코드를 작성하면 됩니다.

for (int i = 1; i <= M; i++)
{
    for (int j = 1; j <= C; j++)
    {
        DT[i][j] = MAX(DT[i][j - 1], arr[i][j]);
        for (int k = 1; k <i; k++)
            DT[i][j] = MAX(DT[i][j], DT[k][j - 1] + arr[i - k][j]);
 
    }
}