[백준] 13156 Selling CPUs - Java

 

 

 

입력을 먼저 해석하자.

 

5 3
1 4 10 1 1
1 1 8 1 1
1 1 9 1 1

 

 

5개의 CPU를 받았고 3명의 상인이 있다.

 

1번 상인) CPU를 한 개 팔 때는 1원을 준다 / 두 개 팔 때는 4원을 준다 / 세 개 팔때는 10원을 준다 ...

2번 상인) CPU를 한 개 팔 때는 1원을 준다 / 두 개 팔 때는 1원을 준다 / 세 개 팔 때는 8원을 준다 ..

3번 상인도 위와 마찬가지이다.

 

상인은 1번부터 순서대로 만나야 하고, 거래도 한 번만 할 수 있다.

 

dp[i][j] = i번 상인을 만나고 있고, j개의 CPU를 팔았을 때 얻는 이익의 최댓값

 

 

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

public class Main {			
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));								

		StringTokenizer st = new StringTokenizer(br.readLine());

		int C = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());

		int[][] dp = new int[M + 1][C + 1];
		int[][] arr = new int[M + 1][C + 1];

		for(int i=1; i<M+1; i++){
			st = new StringTokenizer(br.readLine());			
			for(int j=1; j<C+1; j++){
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		for(int i=1; i<M+1; i++){
			for(int j=1; j<C+1; j++){				
				dp[i][j] = Math.max(dp[i-1][j], arr[i][j]);

				for(int k=1; k<j; k++){
					dp[i][j] = Math.max(dp[i][j], dp[i-1][k] + arr[i][j-k]);
				}
			}
		}

		System.out.println(dp[M][C]);
		
		
	}	
}