문제접근
•
규칙성을 발견
p[6]부터 구하고자 하는 값의 전의 값과 맨 처음값의 합을 통해서 구할 수 있다는 것을 알 수 있음
→ p[n] = p[n-1] + p[i++]
//pseudo code
cin >> t;
cin >> n;
dp[5]까지는 초기화
while // n까지 구함
dp[i] = dp[i-1] + dp[j++]
C++
복사
놓쳤던 부분
•
자료형을 신경쓰지 못 했음
코드
2016 KB
0 ms
#include <iostream>
#include <vector>
int t;
std::vector<long long> dp;
void input_setting()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
}
void solution()
{
int n;
int i, j;
i = 5;
j = 0;
std::cin >> n;
dp.resize(n + 1);
dp[1] = 1;
dp[2] = 1;
dp[3] = 1;
dp[4] = 2;
dp[5] = 2;
while (++i <= n)
dp[i] = dp[i - 1] + dp[++j];
std::cout << dp[n] << "\n";
}
void input()
{
std::cin >> t;
while (t--)
solution();
}
int main(void)
{
input_setting();
input();
return (0);
}
C++
복사
