기업 투자 문서
이런 류의 확장 방법은 하나씩 녹여가면서 큰 덩어리를 만들어간다.
이 하나를 큰 덩이에 녹이는 것이 유리한 가 아니면 버리는 것이 유리한가를 판단하면서
확장 .... 최종적으로 전체를 고려한 큰 덩이를 만든다.
- A 기업에서 답을 구하고
- 이를 이용하여 A,B 기업 기업에서 답을 구하고
- 이를 이용하여 마지막 A,B,C 기업으로 확장하면서 답을 구함.
A+B 기업에서 투자 금액별 최대 이윤을 알고있다고 할 때 ( 그림에서 box )
A+B+C 기업에서 j 원을 투자할 경우 최대 이윤은 .....
- C 에 0 A+B 에 j
- C 에 1 A+B 에 j-1
- ....
- C 에 j A+B 에 0
이 중 최대가 A+B+C 기업에서 J 원을 투자한 경우 최대 이윤이다.
자세한 해 설
| | A | B | C |
| 0 | 0 | 0 | 0 |
| 1 | 2 | 1 | 3 |
| 2 | 5 | 4 | 4 |
| 3 | 7 | 9 | 9 |
| 4 | 8 | 11 | 10 |
- 4 원을 투자할 경우 , A 기업만 있다고 할때 투자 금액별 이윤을 구하면
- 이를 이용하여 A,B 기업에서 투자 금액별 최대이윤을 구해보자.
- 0 원을 투자할 경우에 가능한 모든 경우를 생각하면
- A 기업 0 원 투자 + B 기업 0 원 투자 = 0 + 0
- 1 원을 투자할 경우에 가능한 모든 경우를 생각하면
- A 기업 0 원 투자 + B 기업 1 원 투자 = 0 + 1
- A 기업 1 원 투자 + B 기업 0 원 투자 = 2 + 0
이중 최대값 2 가 A,B 기업에 1 원을 투자할 경우 최대 이윤
- 2 원을 투자할 경우에 가능한 모든 경우를 생각하면
- A 기업 0 원 투자 + B 기업 2 원 투자 = 0 + 4
- A 기업 1 원 투자 + B 기업 1 원 투자 = 2 + 1
- A 기업 2 원 투자 + B 기업 0 원 투자 = 5 + 0
이중 최대 5 가 A,B 기업에 2 원을 투자할 경우 최대 이윤
- 3 원을 투자할 경우에 가능한 모든 경우를 생각하면
- A 기업 0 원 투자 + B 기업 3 원 투자 = 0 + 9
- A 기업 1 원 투자 + B 기업 2 원 투자 = 2 + 4
- A 기업 2 원 투자 + B 기업 1 원 투자 = 2 + 1
- A 기업 3 원 투자 + B 기업 0 원 투자 = 7 + 0
이중 최대 9 이 A,B 기업에 3 원을 투자할 경우 최대 이윤
- 4 원을 투자할 경우에 가능한 모든 경우를 생각하면
- A 기업 0 원 투자 + B 기업 4 원 투자 = 0 + 11
- A 기업 1 원 투자 + B 기업 3 원 투자 = 2 + 9
- A 기업 2 원 투자 + B 기업 2 원 투자 = 5 + 4
- A 기업 3 원 투자 + B 기업 1 원 투자 = 7 + 1
- A 기업 4 원 투자 + B 기업 0 원 투자 = 8 + 0
이중 최대 11 이 A,B 기업에 4 원을 투자할 경우 최대 이윤
- 마지막으로 A,B,C 기업에서 투자 금액별 최대이윤을 구하면
- 0 원을 투자할 경우에 가능한 모든 경우를 생각하면
- A,B 기업 0 원 투자 + C 기업 0 원 투자 = 0 + 0
- 1 원을 투자할 경우에 가능한 모든 경우를 생각하면
- A,B 기업 0 원 투자 + C 기업 1 원 투자 = 0 + 3
- A,B 기업 1 원 투자 + C 기업 0 원 투자 = 2 + 0
이중 최대 3 이 A,B,C 기업에 1 원을 투자할 경우 최대 이윤
- 2 원을 투자할 경우에 가능한 모든 경우를 생각하면
- A,B 기업 0 원 투자 + C 기업 2 원 투자 = 0 + 4
- A,B 기업 1 원 투자 + C 기업 1 원 투자 = 2 + 3
- A,B 기업 2 원 투자 + C 기업 0 원 투자 = 5 + 0
이중 최대 5 가 A,B,C 기업에 2 원을 투자할 경우 최대 이윤
- 3 원을 투자할 경우에 가능한 모든 경우를 생각하면
- A,B 기업 0 원 투자 + C 기업 3 원 투자 = 0 + 9
- A,B 기업 1 원 투자 + C 기업 2 원 투자 = 2 + 4
- A,B 기업 2 원 투자 + C 기업 1 원 투자 = 5 + 2
- A,B 기업 3 원 투자 + C 기업 0 원 투자 = 9 + 0
이중 최대 9 이 A,B,C 기업에 3 원을 투자할 경우 최대 이윤
- 4 원을 투자할 경우에 가능한 모든 경우를 생각하면
- A,B 기업 0 원 투자 + C 기업 4 원 투자 = 0 + 10
- A,B 기업 1 원 투자 + C 기업 3 원 투자 = 2 + 9
- A,B 기업 2 원 투자 + C 기업 2 원 투자 = 5 + 4
- A,B 기업 3 원 투자 + C 기업 1 원 투자 = 9 + 3
- A,B 기업 4 원 투자 + C 기업 0 원 투자 = 11 + 0
이중 최대 12 이 A,B 기업에 4 원을 투자할 경우 최대 이윤
이를 프로그램하기 위해서 식(규칙)을 세워보자. 기업수를 m , 총 투자금액을 n 이라 하자.
각 기업의 투자금액 별 이윤을 가지고 있는 배열을 data[][] 배열이라
하면 이 배열 data[i][j] 는 i 번째 기업에 j 원을 투자할 경우의 이윤으로
문제에서 주어진다.
첫 번째 기업 ~ i 번째 기업에서 j 원을 투자할 경우의
최대이윤은 answer[i][j] 는
점화식:
- answer[i][j] = max( answer[i-1][k] + data[i][j-k] ) 단 ,0<= k <= j
답
시간 복잡도
O(n^3)