백준 알고리즘 문제풀이
문제 9095
#include <iostream>
#include <vector>
std::vector<int> dp_vector;
std::vector<int> dp_input;
int n;
void output()
{
for (int i = 0 ; i < n ; i++)
std::cout << dp_vector[dp_input[i]] << '\n';
}
void solution()
{
dp_vector[1] = 1;
dp_vector[2] = 2;
dp_vector[3] = 4;
for (int i = 0 ; i < n ; i++)
for (int j = 4 ; j <= dp_input[i]; j++)
dp_vector[j] = dp_vector[j - 3] + dp_vector[j - 2] + dp_vector[j - 1];
}
void input()
{
int MAX = 0;
std::cin >> n;
dp_input.resize(n);
for (int i = 0 ; i < n ; i++)
{
std::cin >> dp_input[i];
MAX = std::max(MAX, dp_input[i]);
}
dp_vector.resize(MAX);
}
void preset()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::cout.tie(NULL);
}
int main()
{
preset();
input();
solution();
output();
}
C++
복사
문제 1003
#include <iostream>
#include <vector>
std::vector<int> dp_vector;
std::vector<int> input_vector;
int MAX;
int n;
void output()
{
for (int i = 0 ; i < n ; i++)
{
if (!input_vector[i])
std::cout << "1 0\n";
else
std::cout << dp_vector[input_vector[i] - 1] << " " << dp_vector[input_vector[i]] << '\n';
}
}
void solution()
{
dp_vector[0] = 0;
dp_vector[1] = 1;
for (int j = 2; j <= MAX; j++)
dp_vector[j] = dp_vector[j - 2] + dp_vector[j - 1];
}
void input()
{
std::cin >> n;
input_vector.resize(n);
for (int i = 0 ; i < n ; i++)
{
std::cin >> input_vector[i];
MAX = std::max(MAX, input_vector[i]);
}
dp_vector.resize(MAX + 1);
}
void preset()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::cout.tie(NULL);
}
int main()
{
preset();
input();
solution();
output();
}
C++
복사
