📙[Algo] BOJ2662. 기업 투자

https://www.acmicpc.net/problem/2662

문제 요약

• 만원 단위로 각 기업에 투자할 수 있다
• 돈을 투자하게 되면 얻게되는 이익도 있다.
• 투자액이 정해져 있고, 기업의 개수와 각 기업에 투자했을 때 얻는 이익이 주어질 때, 가장 많이 얻을 수 있는 투자방식과 그때의 이익금을 구하라

시간 제한

• 1초

입력

• 투자 금액 N과 투자 가능한 기업들 개수 M
  • 1 ≤ N ≤ 300, 1 ≤ M ≤ 20
• N개의 줄에 투자액수와 각 기업이 투자가에게 주는 이익이 주어진다.
  • 투자 금액은 항상 1~N
  • 같은 투자금액이 두 번이상 주어지지 X ⇒ i번째 줄에 주어지는 투자 금액은 i-1만원

출력

• 얻을 수 있는 최대 이익 출력
• 각 기업에 투자한 액수 출력

접근법

• 재귀DP로 접근했고, 매개 변수로 현재 갖고 있는 금액 remain과 현재 가리키는 기업 번호 cur을 넘겼다.
  • 즉, 매 케이스마다 현재 remain원이고, cur번째 기업을 가리킬 때 가장 최대로 얻을 수 있는 이익을 찾게된다.
  • 따라서, 0원~reamin원까지 투자하는 케이스를 보게되므로, N^(remain*cur)만큼의 경우의 수를 살펴야 한다. ⇒ dp배열에 메모이제이션 수행
  • 종료조건은 M개의 기업을 모두 탐방했을 때이므로 cur가 M이상일 때 종료했다.(기업 번호를 0번부터 시작했다)
  • 또한, 이 문제에서 각 기업에 투자한 금액을 찾아야 해서, 바로 Math.max로 최댓값을 갱신하지 않았고, 현재까지 저장된 이익(ret)보다 클 경우에만, 최댓값 갱신후 log배열에 현재 투자한 금액을 저장했다.
    • log배열은 remain원이 남았을 때, cur번 기업을 가리킬 때 투자한 금액을 저장하게 된다.
• 재귀를 다 돌고 난 뒤에 반환값은 최대이익이 되고, 각 기업에 투자한 금액을 알기 위해 log배열을 사용해야 한다.
  • 이때, 우리가 탑다운으로 log배열에 기록했기 때문에,
    • log[N][0]일 때, 0번째 기업에 투자한 금액이 sum이라면
    • 그 다음 기업은 log[N-sum][1]…. 이런식으로 각 기업에 투자한 금액을 찾아가야한다.
    • 이거는 재귀dp로 풀었기 때문에, N부터시작해서 각 케이스마자 가장 최적의 경우를 기록했다는 걸 생각해야한다…
      • 즉, log[N][0]은 최대이익을 얻기 위해, 0번 기업에 투자한 금액이 저장될 것이고, 그 다음 1번 기업은 0번 기업에 투자한 금액을 뺀 나머지 금액에서 1번 기업의 투자 금액을 찾아야한다…

코드

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

public class Main {
    static int N, M;
    static int[][] arr;
    static int[][] log;
    static int[][] dp;

    static int recur(int remain, int cur) {
        // remain : 현재 갖고있는 금액
        // cur : 가리키는 회사 번호

        if (cur >= M) return 0;
        if (dp[remain][cur] != -1) return dp[remain][cur];

        int ret = 0, tmp;
        for (int i = 0; i <= remain; i++) {
            // i원 만큼 투자
            tmp = recur(remain - i, cur + 1) + arr[i][cur];
            if (ret < tmp) {
                ret = tmp;
                log[remain][cur] = i;
            }
        }
        dp[remain][cur] = ret;
        return ret;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new int[N + 1][M];
        log = new int[N + 1][M];
        dp = new int[N + 1][M];
        for (int[] d : dp) {
            Arrays.fill(d, -1);
        }
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            st.nextToken();
            for (int j = 0; j < M; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        StringBuilder sb = new StringBuilder();
        int ret = recur(N, 0);
        sb.append(ret).append("\\n");
        int sum = N;
        for (int i = 0; i < M; i++) {
            sb.append(log[sum][i]).append(" ");
            sum -= log[sum][i];
        }
        System.out.println(sb);
    }
}