2662 기업 투자 - 백준

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

2662번: 기업투자

풀이

첫째 줄

N: 투자 금액 M: 투자 가능한 기업들의 갯수

N개의 줄

번호 투자액 기업이익

 

4 2
1 5 1
2 6 5
3 7 9
4 10 15

 

투자금액/기업	1	2
1	5	1
2	6	5
3	7	9
4	10	15

 

 

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

dp[N][M]은 최대값

path[N][M]은 M기업에 얼마나 투자했는가가 저장되어 있음

dp 표

금액/기업	1		2
	dp	path	dp	path
1	5	1	5	0(1:1, 2:0)
2	6	2	6	0(1:2,2:0)
3	7	3	10	2(1:1, 2:2)
4	10	4	15	3(1:0,2:4)

 

dp[4][2] = 15 = 기업 1에 0을 투자해서 0 얻음 + 기업 2에 4를 투자해서 15 얻음

 

path[4][2]=3 = 1-4기업에서 4원으로 최대 이익을 얻을 때 4기업 투자한 금액은 4

 

점화식

dp[i+k][j] = dp[k][j-i] + path[i][j]

path[i + k][j] = i

코드

package test2662;

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

public class Main {

	static int N; // 예산
	static int M; // 기업
	static int invest[][]; // x회사에 k원 투자할 때 얻는 가격
	static int info[][]; // 각 회사의 재화 투입별 가격 앞: 재화, 뒤: 회사 번호, 값: 가격
	static int dp[][]; // 1~j번째 기업까지 i원을 사용했을 경우 최대 이익구하고자 하는 값
	static int[] path;; // dp[x][k]를 최대로 만드는 x에서 투자한 금액

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		MyScanner sc = new MyScanner(System.in);

		N = sc.nextInt();
		M = sc.nextInt();

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

		for (int i = 1; i <= N; ++i) {
			sc.nextInt();
			for (int j = 1; j <= M; ++j) {
				info[i][j] = sc.nextInt();
			}
		}

		solve();
		getPath(N, M);

		sc.write(dp[N][M] + "\n");
		for (int i = 1; i <= M; ++i) {
			sc.write(path[i] + " ");
		}

		sc.close();

	}

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

	public static void getPath(int n, int m) {
		path[m] = invest[n][m]; //m에 투자한 가격은 x회사에 k원 투자할 때 얻는 가격(invest)
		if (m > 0) { // 0번째 기업은 없기 때문에 예외 처리
			getPath(n - path[m], m - 1); // n 재화에서 m투자한 가격을 뺀것은 m-1번째 회사까지의 투자할 때 얻는 가격을 표시하게 된다.(invest)
		}
	}

	static class MyScanner {
		final BufferedReader reader;
		final BufferedWriter writer;
		static StringTokenizer tokenizer = null;

		MyScanner(InputStream in) {
			reader = new BufferedReader(new InputStreamReader(in));
			writer = new BufferedWriter(new OutputStreamWriter(System.out));
		}

		String nextToken() throws IOException {
			if (tokenizer == null || !tokenizer.hasMoreTokens()) {
				tokenizer = new StringTokenizer(reader.readLine());
			}

			return tokenizer.nextToken();
		}

		int nextInt() throws NumberFormatException, IOException {
			return Integer.parseInt(nextToken());
		}

		long nextLong() throws NumberFormatException, IOException {
			return Long.parseLong(nextToken());
		}

		void write(String sb) throws IOException {
			writer.write(sb);
		}

		void close() throws IOException {
			reader.close();
			writer.close();
		}
	}
}