[240710] BOJ 2662 기업투자

문제

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

 

소스코드

(접은글을 열어주세요)

 

package Week_25.BOJ_2662;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.StringTokenizer;

public class BOJ_2662 {

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

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        // 각 투자금 input을 받는다
        int[][] arr = new int[n + 1][m];
        int tmp;
        for (int i = 1; i < n + 1; i++) {
            st = new StringTokenizer(br.readLine());
            tmp = Integer.parseInt(st.nextToken());
            for (int j = 0; j < m; j++) {
                arr[tmp][j] = Integer.parseInt(st.nextToken());
            }
        }

        // dp 배열을 채워나간다.
        // 기업 번호 i >> 해당 기업의 투자금 (j) >> 채워 나갈 금액 (k)
        int[][][] dp = new int[m + 1][n + 1][2];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n + 1; j++) {
                for (int k = n; k >= 0; k--) {
                    if (k - j < 0) break; // 채워나갈 금액보다 해당 기업의 투자금이 커서는 안된다.
                    if (dp[i + 1][k][0] < dp[i][k - j][0] + arr[j][i]) {
                        dp[i + 1][k][0] = dp[i][k - j][0] + arr[j][i];  // 수익금 갱신
                        dp[i + 1][k][1] = j;                            // 해당 기업의 투자금 기록
                    }
                }
            }
        }


        StringBuilder sb = new StringBuilder();

        // 투자금 백트래킹 과정
        ArrayDeque<Integer> q = new ArrayDeque<>();
        tmp = n;
        for (int i = m; i > 0; i--) {
            q.offerFirst(dp[i][tmp][1]);
            tmp -= q.peekFirst();
        }

        sb.append(dp[m][n][0]).append("\n");

        for (Integer i : q) {
            sb.append(i).append(" ");
        }

        System.out.println(sb);
    }
}

소요시간

50분

알고리즘

DP

풀이

• 문제 이해
  • 정해진 투자액 N을 M개의 기업에 나누어 투자해야 한다.
    • 이 때, 어떤 기업에 0원을 투자할 수도, N을 모두 투자할 수도 있다.
    • 각 기업마다 투자액에 따른 이익이 주어진다.
    • 가장 많은 이익을 얻을 때의 이익금과, 이 때 각 기업에 얼마나 투자했는지를 구해야 한다.
  • 한 기업에 투자한 금액은 다른 기업에 투자할 수 있는 금액에 영향을 주니 DP를 사용하여 풀이할 수 있다.
• 접근 과정
  • 각각의 기업에 대해, 0~n까지의 금액을 투자할 수 있도록 (m+1)*(n+1)*2의 dp 배열을 만든다.
    • 이 때, *2로 3차원 배열을 만드는 이유는 이후 각각의 기업에 얼마나 투자하였는지 트래킹하기 위함이다.
  • m개의 기업을 차례대로 확인한다. 이 때 기업 번호를 i로 둔다
  • i번째 기업에 투자를 j만큼 하여 0부터 i번째 기업까지 투자한 투자금의 총액이 k가 되도록 dp 배열을 채워 나간다.
    • 이 때, j는 k보다 클 수 없다.
    • dp[i+1][k]에서,
      • 0번째 인덱스에는 i번째 기업까지 총 k의 투자금을 투자했을때 얻을 수 있는 최대 이익금을 넣는다.
      • 1번째 인덱스에는 이번 갱신에서 i번째 기업에 투자한 금액 j를 기록한다.
  • dp 배열을 통해 m개의 기업에 n만큼의 투자금을 썼을때의 총 금액 dp[m][n][0]을 출력한다.
  • 또한 dp배열의 인덱스 1을 역으로 추적하여 각각의 기업에 대한 투자금을 구하여 출력한다.