9461번: 파도반 수열

문제접근🤔

• 규칙성을 발견

  https://apption.co/embeds/jdp071

  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++]

놓쳤던 부분😅

• 자료형을 신경쓰지 못 했음

코드😁

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);
}