BOJ 7579 - 앱 (knapsack[+])

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

2차원 구조->1차원 구조 설명

한 동전을 단 한번 사용해야 하는지, 여러번 사용할 수 있는지

 

<문제설명>

앱을 끄면  메모리와 비용이 각각 늘어난다. (메모리 <= 1e7, 비용 <= 1e2)

 

총 M의 메모리가 필요할 때, 최소비용을 구해라

 

<풀이1>

dp[k] : 메모리 k를 만드는데 드는 최소비용

~i-1번 앱까지 처리 했을 때, i번 앱을 추가해서 dp배열을 초기화 해준다.

 if(k-b[i]<0) dp[k] = min(dp[k], c[i])       //의미의 통일성을 위함. 최소~이므로(밑 풀이는 최대이므로필요없)

 else dp[k] = min(dp[k], dp[k-b[i]]+c[i])

 

이 때, 앱은 단 한번씩만 끌 수 있으므로 dp배열 뒤부터 초기화 함에 유의. (dp테이블 한번 써보면 바로 이해될 것)

 

 

n<=100 m<=1e7이므로 O(1e9) -> tle 아슬아슬하게 돌아감

<코드>

const int MAX = 1e7+1;
int n, m, b[101], c[101], dp[MAX];
int main() {
	cin >> n >> m;
	fill(dp, dp + MAX, 1e9);
	for (int i = 0; i < n; i++) cin >> b[i]; //메모리
	for (int i = 0; i < n; i++) cin >> c[i]; //비용

	dp[0] = 0;
	for (int i = 0; i < n; i++)
		for (int j = m; j >= 1; j--)
			if(j-b[i]<0) dp[j] = min(dp[j], c[i]);
			else dp[j] = min(dp[j], dp[j - b[i]] + c[i]);

	cout << dp[m] << '\n';
}

---

<풀이2>

dp[k] : 비용 k로 만들 수 있는 최대 메모리

위와 마찬가지로 순서 강제하면

dp[j] = max(dp[j], dp[j-c[i]]+b[i])

 

전처리 후 비용 k이상인 최소 메모리를 찾아주면 된다.

 

<코드>

int n, m, b[101], c[101], dp[10001], ans;

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) cin >> b[i];
	for (int i = 0; i < n; i++) cin >> c[i];

	dp[0] = 0;
	for (int i = 0; i < n; i++)
		for (int j = 10000; j >= c[i]; j--)			
			dp[j] = max(dp[j], dp[j - c[i]] + b[i]);

	for (int i = 0; i <= 10000; i++) if (dp[i] >= m) {
		ans = i;
		break;
	}

	cout << ans << '\n';
}

 

앱을 여러번 조작할 수 있다면 -> 위에 dp 초기화하는 부분을 오름차순으로 초기화