Memo
풀이
두가지 풀이를 생각해 보았는데 로직상으로 다른점은 없다.
입력을 우선적으로 다 받고 로직을 돌리는 것과 입력을 받으면서 연산을 하는 것 중 어떤 것이 더 좋은 코드인지 고민을 해보기 위해서 작성해 보았다.
Code
제출 날짜
@2/23/2021
메모리
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();
}
C++
복사
< 풀이 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();
}
C++
복사
