11052번: 카드 구매하기

Memo

풀이

두가지 풀이를 생각해 보았는데 로직상으로 다른점은 없다.

입력을 우선적으로 다 받고 로직을 돌리는 것과 입력을 받으면서 연산을 하는 것 중 어떤 것이 더 좋은 코드인지 고민을 해보기 위해서 작성해 보았다.

Code

제출 날짜

2021/02/23

메모리

2016 KB

시간

0 ms

< 풀이 1 >

input vector를 받은 후 dp vector 처리

#include <iostream>
#include <vector>

int N;
std::vector<int> arr;
std::vector<int> dp;

void output()
{
	std::cout << dp[N];
}

void solution()
{
	for (int i = 1 ; i <= N ; i++)
	{
		for (int j = 1 ; j <= i ; j++)
			dp[i] = std::max(dp[i], dp[i - j] + arr[j]);
		/************출력용*************
		for (int k = 1 ; k <= N ; k++)
			std::cout << dp[k] << " ";
		std::cout << std::endl;
		***************************/
	}
}

void input()
{
	std::cin >> N;
	arr.resize(N + 1);
	dp.resize(N + 1);
	for (int i = 1 ; i <= N ; i++)
		std::cin >> arr[i];
}

void preset()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);
}

int main()
{
	preset();
	input();
	solution();
	output();
}

< 풀이 2 >

input 을 받는 위치에서 바로 dp vector 연산

#include <iostream>
#include <vector>

int N;
std::vector<int> arr;
std::vector<int> dp;

void output()
{
	std::cout << dp[N];
}

void input_sol()
{
	std::cin >> N;
	arr.resize(N + 1);
	dp.resize(N + 1);
	for (int i = 1 ; i <= N ; i++)
	{
		std::cin >> arr[i];
		for (int j = 1 ; j <= i ; j++)
			dp[i] = std::max(dp[i], dp[i - j] + arr[j]);
	}
}

void preset()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);
}

int main()
{
	preset();
	input_sol();
	output();
}