백준 파도반 수열(9461) C++ 풀이

알고리즘 분류

수학

다이나믹 프로그래밍(DP)

 

문제 해결 아이디어

1, 1, 1, 2, 2, 3, 4, 5, 7, 9 ...로 진행되기 때문에 이 패턴을 잘 보면서 4번째부터 n - 3번째 + n - 2번째를 더해 값이 나오는 것을 알 수 있다. 따라서 1,2,3번째를 미리 1로 세팅 후 dp[n - 3] + dp[n - 2]로 해결한다.

 

코드

#include <iostream>
using namespace std;


long long dp[101];
int main()
{
	dp[0] = 0; dp[1] = 1; dp[2] = 1; dp[3] = 1;
	int t, n;

	cin >> t;

	for (int i = 0; i < t; i++)
	{
		cin >> n;
		for (int i = 4; i <= n; i++)
		{
			if (dp[i] != 0) continue;
			dp[i] = dp[i - 3] + dp[i - 2];
		}

		cout << dp[n] << "\n";
	}
}

코드 설명

단순히 입력을 받은만큼 for문을 돌아 dp[i - 3] + dp[i - 2] 공식을 이용해 답을 구하고, 만약 구하려는 값이 dp[i]가 0이 

아니면 이미 구한 값이 때문에 그 계산은 건너뛴다.