카드 구매하기

Memo

접근 방법

인덱스 0부터 N - 1 까지 로직함수의 인자를 차례대로 넣어주고, 로직함수 내에서는 매개변수로 받은 값보다 작은 값을 dp 배열에 누적해 갑니다.

로직을 직관적인 예로 설명드리면,

만약 N이 5이라고 한다면, 카드팩이 5인 경우의 값, 1인 경우와 4인 경우를 더해서 만들어진 값, 2인 경우와 3인 경우를 더해서 만들어진 값. 총 3가지 경우의 최댓값이 됩니다. 이때 4인 경우는 1과 3, 2와 2, 4 로 만들 수 있는 최대값으로 만들 수 있습니다.

따라서 dp 배열을 만든 후에 앞에서 부터 차례대로 쌓아 나가면 문제를 쉽게 해결할 수 있습니다.

Code

제출 날짜

2021/02/23

메모리

2016 KB

시간

0 ms

#include <iostream>
#include <vector>

size_t N;
std::vector<int> P;

void input_faster()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
}

void input()
{
	input_faster();
	std::cin >> N;
	P.resize(N + 1);
	for (size_t i = 1 ; i < N + 1 ; i++)
		std::cin >> P[i];
}

void logic(size_t ind)
{
	size_t max_ = ind / 2;
	int tmp;

	for (size_t i = 1 ; i <= max_ ; i++)
	{
		if (P[ind] < (tmp = P[i] + P[ind - i]))
			P[ind] = tmp;
	}
}

void solve()
{
	for (size_t i = 1 ; i < N + 1 ; i++)
		logic(i);
}

void print_val()
{
	std::cout << P[N];
}

int main()
{
	input();
	solve();
	print_val();
	return (0);
}