[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보다 작다.

접근 방법

최대 이익을 구하기 위한 조건을 분석해 정리해 보면 다음과 같습니다.

1. 현재 선택한 기업 i에 j만원을 투자하는 경우 최대 이익값
2. 현재 기업 전까지 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);
    }
}

결과