7579 app

์•Œ๊ณ ๋ฆฌ์ฆ˜(๋ฐฐ๋‚ญ์ •๋ฆฌ, DP)

1. ๋ฐฐ๋‚ญ์ •๋ฆฌ ์‘์šฉ. ์ตœ๋Œ€ ๋น„์šฉ์„ ๊ฐ€๋ฐฉ์— ๋‹ด์„ ์ˆ˜ ์žˆ๋Š” ์ตœ๋Œ€ ๋ฌด๊ฒŒ๋กœ ๋ณด๊ณ , ๋ฉ”๋ชจ๋ฆฌ๋ฅผ ๊ฐ€์น˜๋กœ ๋ณธ๋‹ค
2. ์ด๋ ‡๊ฒŒ 2์ฐจ์› ๋ฐฐ์—ด์„ ์™„์„ฑํ•˜๊ณ , ํ•„์š”ํ•œ ๋ฉ”๋ชจ๋ฆฌ ์ด์ƒ์ด๋ฉฐ ๋น„์šฉ์ด ์ตœ์†Œ์ธ ์นธ์„ ํŒ๋ณ„ํ•˜๊ณ  ์ถœ๋ ฅํ•˜๋ฉด ๋œ๋‹ค.

๊ตฌํ˜„๋ฒ•

1. ์ตœ๋Œ€ ์•ฑ ๊ฐœ์ˆ˜๋Š” 100๊ฐœ์ด๋ฏ€๋กœ, 101ํ–‰, ์•ฑ ๋‹น ์ตœ๋Œ€ ๋น„์šฉ์€ 100 ์ด๋ฏ€๋กœ 10001์—ด์„ ์„ ์–ธํ•˜์—ฌ ๊ตฌํ˜„ํ•˜๋ฉด ๋จ.
2. 2์ฐจ์› ๋ฐฐ์—ด ์™„์„ฑํ•˜๊ณ ๋‚˜์„œ๋Š” ์ฒซ๋ฒˆ์งธ ์›์†Œ๋ถ€ํ„ฐ ๊ฒ€์‚ฌํ•˜์—ฌ, ๋ฉ”๋ชจ๋ฆฌ๊ฐ€ ํ•„์š”์ด์ƒ์œผ๋กœ ์žˆ๋Š”๋ฐ, ๋น„์šฉ์ด ์ตœ์†Œ์ธ ๊ฒƒ์„ ์ฐพ์œผ๋ฉด ๋จ.

์ฝ”๋“œ

#include <iostream>
#define MAX_N 100
#define MAX_MEMORY 10000000
 
using namespace std;
 
int numOfApp, a[MAX_N], c[MAX_N], m, maxValue;
int DP[105][10020];
 
int getMin();
int max(int a, int b) {
	return a > b ? a : b;
}
 
int main() {
	cin >> numOfApp >> m;
	for (int i = 0; i < numOfApp; i++)
		cin >> a[i];
	for (int i = 0; i < numOfApp; i++) {
		cin >> c[i];
		maxValue += c[i];
	}
 
	cout << getMin();
}
 
int getMin(){
	for (int i = 1; i <= numOfApp; i++) {
		for (int j = 1; j <= maxValue; j++) {
			if (c[i-1] > j)
				DP[i][j] = DP[i - 1][j];
			else
				DP[i][j] = max(a[i-1] + DP[i - 1][j - c[i-1]], DP[i - 1][j]);
		}
	}
 
	int minValue = 2000000000;
	for (int i = 0; i <= numOfApp; i++) {
		for (int j = 0; j <= maxValue; j++) {
			if (DP[i][j] >= m && minValue > j)
				minValue = j;
		}
	}
	return minValue;
}