[BAEKJOON] 7579번 : 앱

문 제

 

소 스  코 드

#include <iostream>
#include <algorithm>

constexpr int MAX{ 100 };
constexpr int COSTMAX{ 10'000 };

typedef std::pair<int, int> App;

App apps[MAX]{std::make_pair(0, 0),};
int dp[COSTMAX]{ 0, };


int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	int N, M;
	std::cin >> N >> M;


	int maxCost{ 0 };
	for (int i = 0; i < N; ++i) std::cin >> apps[i].first;
	for (int i = 0; i < N; ++i) {
		std::cin >> apps[i].second;
		maxCost += apps[i].second;
	}

	for (int i = 0; i < N; ++i) {
		for (int j = maxCost; j >= apps[i].second; --j) {
			dp[j] = std::max(dp[j], dp[j - apps[i].second] + apps[i].first);
		}
	}

	for (int i = 0; i < maxCost; ++i) {
		if (M <= dp[i]) {
			std::cout << i << '\n';
			break;
		}
	}

	return 0;
}

 

풀 이

 

• [BAEKJOON] 12865번 평범한 배낭

평범한 배낭과 비슷한 유형의 문제이다.

 

누적된 결과 이기 때문에, 

 

dp[cost] = Max(dp[cost], dp[cost - cost[i]]] + memory[i])

를 통하여 누적된 값을 찾아 구할 수 있다.

for문을 maxCost ~ cost[i] 까지 -- 동작을 해야 이전 동작에 상관없이 올바른 결과를 찾을 수 있다.

 

 

출 력 값

 

 

문 제  출 처

문제 링크 : https://www.acmicpc.net/problem/7579

7579번: 앱