기업투자(정올 1825,백준2662)

 

문제링크

http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1098&sca=99&sfl=wr_hit&stx=1825 

JUNGOL

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

2662번: 기업투자

코드

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

public class Main {
	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());
		int m=Integer.parseInt(st.nextToken());
		int n=Integer.parseInt(st.nextToken());
		int[][] dp=new int[n+1][m+1];
		int[][] pay=new int[n+1][m+1];
		int[][] path=new int[n+1][m+1];
		for(int i=1;i<=m;i++) {
			st=new StringTokenizer(br.readLine());
			int idx=Integer.parseInt(st.nextToken());
			for(int j=1;j<=n;j++) {
				pay[j][idx]=Integer.parseInt(st.nextToken());
			}
		}
		for(int i=1;i<=n;i++) {
			for(int cost=1;cost<=m;cost++) {
				for(int now=0;now<=cost;now++) {
					int temp=pay[i][now]+dp[i-1][cost-now];
					if(temp>dp[i][cost]) {
						dp[i][cost]=temp;
						path[i][cost]=now;
					}
				}
			}
		}
		//----------------입력
		System.out.println(dp[n][m]);
		int y=n;
		int x=m;
		String ans="";
		while(y>0) {
			ans=path[y][x]+" "+ans;
			x-=path[y][x];
			y--;
		}
		System.out.println(ans);
	}
}