BOJ 2662 - 기업투자

문제 접근

Bottom-Up 방식의 배낭(Knapsack) 알고리즘으로 접근했다.

---

DP 정의

dp[i][j] = j번째 기업까지 고려하여, i만원을 투자했을 때의 최대 이익

---

점화식

for (int i = 1; i < M; i++) {
    for (int j = 1; j <= N; j++) {
        for (int k = j; k != -1; k--) {
            dp[j][i] = Math.max(dp[j][i], dp[j - k][i - 1] + invest[k][i]);
        }
    }
}

• k는 i번째 기업에 투자할 금액
• 나머지 j - k만원은 이전 기업들(i - 1번째까지)에서 최적으로 분배

---

경로 추적 (Track)

최대 이익뿐만 아니라 각 기업에 얼마를 투자했는지도 출력해야 한다.

track[i][j]에 j번째 기업에 투자한 금액을 기록해두면 된다.

for (int i = 1; i < M; i++) {
    for (int j = 1; j <= N; j++) {
        int select = 0;

        for (int k = j; k != -1; k--) {
            if (dp[j][i] < dp[j - k][i - 1] + invest[k][i]) {
                select = k;
                dp[j][i] = dp[j - k][i - 1] + invest[k][i];
            }
        }

        track[j][i] = select; // j번째 기업에 k만원 투자
    }
}

---

역추적

track[N][M-1]에서 시작해 뒤에서부터 추적한다.

Stack을 사용하는 이유는 끝에서부터 추적하기 때문에, 꺼낼 때 역순으로 출력할 수 있기 때문이다.

for (int i = M - 1; i != -1; i--) {
    stack.add(track[N][i]);
    N -= track[N][i];
}

while (!stack.isEmpty()) {
    bw.write(stack.pop() + " ");
}

---

시간 복잡도

$O(N^2 \times M)$

• N = 300, M = 20 기준으로 계산하면 약 90만 번 연산
• 실제로는 k가 j부터 0까지 줄어들므로 $\frac{n(n+1)}{2}$ 형태로 절반 수준

---

전체 코드

import java.util.*;
import java.io.*;

public class Main {
    static int N;
    static int M;
    static int[][] dp;
    static int[][] invest;
    static int[][] track;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        dp = new int[N + 1][M];
        invest = new int[N + 1][M];
        track = new int[N + 1][M];

        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            st.nextToken(); // 투자 금액 인덱스 버리기
            for (int j = 0; j < M; j++) {
                invest[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // 기업이 1개일 때 초기화
        for (int j = 1; j <= N; j++) {
            dp[j][0] = invest[j][0];
            track[j][0] = j;
        }

        for (int i = 1; i < M; i++) {
            for (int j = 1; j <= N; j++) {
                int select = 0;

                for (int k = j; k != -1; k--) {
                    if (dp[j][i] < dp[j - k][i - 1] + invest[k][i]) {
                        select = k;
                        dp[j][i] = dp[j - k][i - 1] + invest[k][i];
                    }
                }

                track[j][i] = select;
            }
        }

        bw.write(dp[N][M - 1] + "\n");

        Stack<Integer> stack = new Stack<>();
        for (int i = M - 1; i != -1; i--) {
            stack.add(track[N][i]);
            N -= track[N][i];
        }

        while (!stack.isEmpty()) {
            bw.write(stack.pop() + " ");
        }

        bw.flush();
        bw.close();
    }
}