(백준 11052번 카드 구매하기 C++) 라이님 블로그 대회 알고리즘 따라잡기 5) DP(Dynamic Programming) 동적계획법 4탄

한달만에 복귀했다ㅎㅎ 이번주 DP 예제문제 다 뽀개고 다음 알고리즘으로 고고!!

 

백준 11052번

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

11052번: 카드 구매하기

문제 자체는 어렵지 않다. 

f(n)을 n개의 카드에 사는데 드는 최대의 금액이라고 정의하면

f(n)은 f(n-1) + (1개의 카드에 지불할 최대 금액), f(n-1) + (2개의 카드에 지불할 최대의 금액), ... ,(f(1) + (n-1)개의 카드에 지불할 최대의 금액) 중 가장 큰 금액이 된다.

 

그러면 점화식 f(n) = max(f(n-i) + f(i)) (1 < i < n)으로 나타낼 수 있고, DP로 문제를 풀면 아래와 같다.

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX_N = 1001;
int N, cost[MAX_N], DP[MAX_N];

int f(int n) {
	if (DP[n] != -1) return DP[n];
	
	int result = cost[n];
	for (int i = 1; i < n; i++)
		result = max(result, f(i) + f(n - i));
	DP[n] = result;
	return result;
}
int main() {
	scanf("%d", &N);
	for (int i = 1; i < N+1; i++) scanf("%d", &cost[i]);
	for (int i = 1; i < N+1; i++) DP[i] = -1;
	DP[0] = 0;
	DP[1] = cost[1];
	int ans = f(N);
	printf("%d", ans);
	return 0;
}

 

 

 

 

오랜만에 백준을 푸니까 아이디어가 빠르게 나오지 않아 아쉽다..

꾸준히 뽀개야겠따!!!!🔥🔥