[백준] 26607 시로코와 은행털기 [자바]

 

 

---

https://upload.acmicpc.net/42e779b9-a313-4076-a157-510f8a708aa3/

 

※. a+b의 값은 항상 동일하다

(a의 값을 알면 b의 값도 알 수 있다.)

 

※. 종합 능력치는 sum(a) * (x * k - sum(a))

(작업을 다했을 때 sum(a)+sum(b)는 무조건 x*k 다.)

 

※. dp[횟수(k)][합(j)]을 저장하는 boolean 2차원 배열을 선언한다.

(k번 동안 j의 합을 만들 수 있으면 true)

(횟수가 1번부터 k번부터 탐색한다면 같은 능력치가 더해진다. dp[2][3] = true -> 3을 탐색할 때 dp[2][3] = true)

 

※. 같은 능력치가 겹치지 않게 능력치부터 탐색한다.

(현재 능력치가 p일 때 dp[i][j-p]가 참이면 dp[i+1][j](능력치 p를 더한 것, 겹치지 않음) 도 참이다.

(dp탐색을 다 한 뒤 dp[1][p](1개 일 때 p) = true)

 

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
	static boolean[][] dp;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		int x = Integer.parseInt(st.nextToken());
		int[] arr = new int[n];
		dp = new boolean[k+1][x*k+1];
		for(int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			arr[i] = a;
		}
		
		for(int p : arr) { //dp[i][j] i개일때 j가 가능한가
			knapsack(p,k,x);
		}
		int ans = 0;
		for(int i = 0; i <= x*k; i++) {
			if(dp[k][i]) {
				ans = Math.max(ans, i*(x*k-i));
			}
		}
		System.out.println(ans);
	}
	static void knapsack(int p, int k, int x) {
		for(int i = k-1; i >= 1; i--) {
			for(int j = x*k; j >= p; j--) {
				dp[i+1][j] = dp[i+1][j] || dp[i][j-p]; //j-p를 뺀 값이 있다면
			}
		}
		
		dp[1][p] = true;
	}
}