백준 11052번 카드 구매하기

🔒[문제 url]

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

🪄전체 코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream> // cpp
#include <algorithm>
using namespace std;

int n;
int p[1001];
int dp[1001];

void INPUT()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> p[i];
}

int DP(int card)
{
	/*
	* Dynamic Programming
	* 
	* p[i] : i개 카드팩의 가격, dp[i] : i장 샀을때의 최대 가격
	* n == 5일 경우,
	* 5 / 4 1 / 3 2 / 3 1 1 / 2 2 1 / 2 1 1 1 / 1 1 1 1 1 장을 사는 경우중,
	* 최대값이 곧 출력값이 된다.
	* 
	* 5장을 사는 경우,
	* 1. dp[4]+dp[1], dp[3]+dp[2] 중 최대값을 구하고,
	* 2. 1번에서 구한 최대값과 p[5] 를 비교해 더 큰 값이 최대값(dp[5])이 된다.
	* 이때,
	* dp[4]+dp[1], dp[3]+dp[2] 중 최대값을 알기 위해선, 각각의 dp[i]값을 알아하는데,
	* dp[5]와 같은 방식으로
	* dp[4]또한 1, 2번 과정을 통해 구할 수 있다.
	* 
	* 반복문을 통해 1번 과정의 index를 지정해주고, 재귀를 통해 더 작은 index의 dp[i]를 구한다.
	* 2번은 반복문에서의 최대값과 p[i]를 비교해줌으로써 dp[i]를 알게되고,
	* 최종적으로 dp[n]을 반환하게 된다.
	*/


	if (card == 1) return dp[card] = p[card]; // 1장이면 최댓값은 p[1]
	if (dp[card]) return dp[card]; // 알고있는 정보면 바로 return

	
	int MAX = -1;
	for (int i = 1; i <= card / 2; i++)
	{// ex) 2 3과 3 2를 둘 다 할 필요없으므로 i <= card / 2;
    	//최대값 갱신
		int temp = DP(card - i) + DP(i);
		if (dp[card] < temp) dp[card] = temp;
	}

	return dp[card] = max(p[card], dp[card]);
}

void SOLVE()
{
	cout << DP(n);
}

int main()
{
	INPUT();

	SOLVE();
}

🥇문제 후기

GOLD5 미만 난이도는 알고리즘 및 풀이 설명을 주석으로 대체합니다.
주석을 참고해주세요.