[BOJ 2662] 기업 투자 (Java 풀이)
문제
어떤 투자가가 여러 기업들에게 돈을 투자해서 최대의 이익을 얻고자 한다. 단, 투자는 만원 단위로 할 수 있으며 각 기업은 많이 투자할수록 많은 이익을 투자가에게 돌려준다.
돈을 투자하지 않은 경우는 당연히 얻게 되는 이익도 없다. 예를 들어서, 한 투자가가 4만원을 갖고 두 개의 기업들에 각각 만원 단위로 투자했을 경우 얻을 수 있는 이익은 다음과 같다.
위의 경우 만일, 기업 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보다 작다.
접근 방법
최대 이익을 구하기 위한 조건을 분석해 정리해 보면 다음과 같습니다.
- 현재 선택한 기업 i에 j만원을 투자하는 경우 최대 이익값
- 현재 기업 전까지 n-j 만원을 투자했을때의 최대 이익 + 현재 선택한 기업 i에 j 만원을 투자했을때의 이익값
- 위의 두 값중 더 큰 값을 계속 저장해 나가자!
이를 조금 더 간단하게 표현해 보면
dp[투자금액][기업] : '0번 기업부터 현재 기업'까지 '투자금액'을 투자할 시 얻을 수 있는 최대 이익
info[투자금액][기업] : 현재 기업에 '투자금액'을 투자할 시 얻을 수 있는 이익들을 저장한 배열
그렇다면 다음과 같이 나타낼 수 있습니다.
(i : 현재 투자할 기업, j : i 기업에 투자할 금액, k : 이전까지 지나온 모든 기업에 투자한 금액의 합)
dp[j+k][i] = Math.max(dp[j+k][i], dp[k][i-1] + info[j][k])
여기서 우리에겐 요구사항이 하나 더 있습니다. 바로 지나온 경로를 출력해 줘야 한다는 것입니다.
경로를 저장하기 위해서 현재 기업에 투자하게 되는 경우 (조건을 만족할 때) 해당 기업에 투자한 금액을 저장해 주어 재귀로 찾아가면 됩니다.
소스 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class CompanyInvest {
static int n, m;
static int[][] dp, info, invest;
static int[] path;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input = br.readLine().split(" ");
n = Integer.parseInt(input[0]); // 투자할 수 있는 자금
m = Integer.parseInt(input[1]); // 기업 개수
invest = new int[n + 1][m + 1];
info = new int[n + 1][m + 1];
dp = new int[n + 1][m + 1];
path = new int[n + 1];
for (int i = 1; i <= n; i++) {
input = br.readLine().split(" ");
for (int j = 1; j <= m; j++) {
int benefit = Integer.parseInt(input[j]);
info[i][j] = benefit;
}
}
findMaxBenefit();
getPath(n, m);
StringBuilder result = new StringBuilder();
result.append(dp[n][m]).append('\n');
for (int i = 1; i <= m; i++) {
result.append(path[i]).append(' ');
}
System.out.println(result);
br.close();
}
public static void findMaxBenefit() {
for (int i = 1; i <= m; i++) {
for (int j = 0; j <= n; j++) {
for (int k = n - j; k >= 0; k--) {
if (dp[k][i - 1] + info[j][i] > dp[j + k][i]) {
dp[j + k][i] = dp[k][i - 1] + info[j][i];
invest[j + k][i] = j;
}
}
}
}
}
public static void getPath(int n, int m) {
if (m == 0) {
return;
}
path[m] = invest[n][m];
getPath(n - path[m], m - 1);
}
}
결과
Author And Source
이 문제에 관하여([BOJ 2662] 기업 투자 (Java 풀이)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@wotj7687/BOJ-2662-기업-투자-Java-풀이저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)