백준 11052번: 카드 구매하기

[문제 링크]

11052번: 카드 구매하기

---

간단한 dp문제였다.

 

Top-down 방식으로 푸는 경우, N개의 카드를 가장 비싸게 구입하는 금액은 카드를 i개 묶음을 구입하는 금액 + N-i개의 카드를 가장 비싸게 구입하는 금액이다. 여기서 i를 1~N까지 반복하여 그 중 최대값을 구해주면 된다.

따라서 점화식은 다음과 같다.

for(i=1; i<=N; i++)

dp(N) = max(dp[N], dp[N-i] + P[i]);

 

Bottom-up 방식으로 푸는 경우, 이중 for문을 통해 구현할 수 있으며 점화식은 Top-down 방식과 동일하다.

---

#include <iostream>
using namespace std;

int P[1001], memo[1001];

inline int max(int a, int b) { return a > b ? a : b; }

int Topdown(int N)
{
	if (N == 0) return 0;

	int& ret = memo[N];
	if (ret != 0) return ret;

	for (int i = 1; i <= N; i++)
		ret = max(ret, Topdown(N - i) + P[i]);

	return ret;
}

int Bottomup(int N)
{
	// memo[0] = 0 으로 초기화 해줘야 하지만 전역변수는 기본값이 0이므로 생략
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= i; j++)
			memo[i] = max(memo[i], memo[i - j] + P[j]);

	return memo[N];
}

int main(void)
{
	int N;
	cin >> N;

	for (int i = 1; i <= N; i++)
		cin >> P[i];

	// top-down
	cout << "Top-down: " << Topdown(N) << endl;

	// Bottom-up
	cout << "Bottom-up: "<< Bottomup(N) << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 70 day