백준 2662 : 기업투자

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

2662번: 기업투자

[ 문제풀이 ]

배낭 문제와 거의 비슷한 유형으로 dp를 사용하여 해결해주면 된다.

먼저 다음과 같이 dp 테이블을 정의하자.

dp[i][j] : 1~j번째 기업까지 i원을 사용했을 경우 최대 이익구하고자 하는 값

 

그렇다면 점화식은 어떻게 될까? 잘 생각해보면 현재 기업에 i원을 투자하기 위해서는 이전 i-1기업까지 투자한 금액이 N-i원을 초과해서는 안된다. 그래야 현재 기업에 i원만큼 투자할 수 있기 때문이다.

즉, j번째 기업에서 i원을 투자할때의 최대 이익은 j-1번째 기업까지 N-i원 이하로 투자한 것들 중에서의 최대 이익 + j번째 기업에서 i원 투자한 금액이다.

이는 다음과 같이 표현할 수 있다.

//j : 기업, i : j기업에 투자할 금액, k : j-1기업까지 투자한 금액
for (int j = 1; j <= M; ++j) {
	for (int i = 0; i <= N; ++i) {
		for (int k = N - i; k >= 0; --k) {
            //j기업까지 i+k원을 투자한 이익보다
            //j-1기업까지 k원을 투자한 이익 + j기업에 i원을 투자한 금액이 더 크다면
			if (dp[i + k][j] < dp[k][j - 1] + info[i][j]) {
				dp[i + k][j] = dp[k][j - 1] + info[i][j];
				invest[i + k][j] = i; //투자 액수 저장(경로를 추적하기 위해)
			}
		}
	}
}

 

각 기업의 투자 방식은 최대 이익이 갱신될때마다 투자한 금액을 저장해 두고 역으로 추적해주면 된다.

최종적인 정답은 dp[N][M]이기 때문에 invest[N][M]에는 M기업에 얼마를 투자했는지가 저장되어있다. 그렇다면 M-1기업에는 얼마를 투자했는지를 알기 위해선 어떻게 해야 할까?

dp 배열에는 최적해가 저장되어있음이 보장되기 때문에 함께 갱신한 invest 배열도 최적해가 저장되어있다. 따라서 M기업에 invest[N][M]원을 투자했기 때문에 M-1기업에는 N원에서 M기업에 투자한 금액만큼 감소한 invest[N - invest[N][M]][M - 1]원을 투자했다는 것을 알 수 있다.

이런식으로 1번째 기업까지의 투자한 금액을 역으로 추적하면 정답을 구할 수 있다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {

	static int N, M;
	static int[][] info, dp, invest;
	static int[] path;
	
	public static void main(String[] args) {
		try (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());
			
			info = new int[N + 1][M + 1];
			invest = new int[N + 1][M + 1];
			path = new int[M + 1];
			for (int i = 1; i <= N; ++i) {
				st = new StringTokenizer(br.readLine());
				st.nextToken();
				for (int j = 1; j <= M; ++j) {
					int benefit = Integer.parseInt(st.nextToken());
					info[i][j] = benefit;
				}
			}
			
			/**
			 * dp[i][j] : 1~j번째 기업까지 i원을 사용했을 경우 최대 이익
			 * 구하고자 하는 값, dp[N][M] : 1~M번째 기업까지 N원을 사용했을 경우 최대 이익
			 */
			dp = new int[N + 1][M + 1];
			
			solve();
			getPath(N, M);
			
			bw.write(dp[N][M] + "\n");
			for (int i = 1; i <= M; ++i) {
				bw.write(path[i] + " ");
			}
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
	
	public static void solve() {
		//j : 기업, i : j기업에 투자할 금액, k : j-1기업까지 투자한 금액
		for (int j = 1; j <= M; ++j) {
			for (int i = 0; i <= N; ++i) {
				for (int k = N - i; k >= 0; --k) {
		            //j기업까지 i+k원을 투자한 이익보다
		            //j-1기업까지 k원을 투자한 이익 + j기업에 i원을 투자한 금액이 더 크다면
					if (dp[i + k][j] < dp[k][j - 1] + info[i][j]) {
						dp[i + k][j] = dp[k][j - 1] + info[i][j];
						invest[i + k][j] = i; //투자 액수 저장(경로를 추적하기 위해)
					}
				}
			}
		}
	}
	
	public static void getPath(int n, int m) {
		if (m == 0) return;
		path[m] = invest[n][m];
		getPath(n - path[m], m - 1);
	}
}