[c++] 9461 파도반 수열

백준 단계별로 풀어보기 [동적계획법 1] 파도반 수열

https://www.acmicpc.net/problem/9461

9461번: 파도반 수열

 

[풀이]

파도반 수열. 1 1 1 2 2 3 4 5 7 9 12 16 ... 이 수열만 보더라도 dp[n] = dp[n-2] + dp[n-3] 이라는 점화식을 구할 수 있다. 다만, 수가 커지면 int 범위를 넘어서기 때문에 int가 아니라 long long으로 선언 해야한다.

6번째 삼각형 = 3번째(1) + 5번째(2)

7번째 삼각형 = 6번째 + 1번째(1)

8번째 삼각형 = 7번째 + 2번째(1)

9번째 삼각형 = 8번째 + 4번째(2) ...

다음의 규칙을 따라 dp[n] = dp[n-5] + dp[n-1] 의 점화식을 이용할 수도 있다.

 

[코드]

#include <iostream>
#include <algorithm>

long long arr[100];

int main() {
	//파도반 수열
	//1 1 1 2 2 3 4 5 7 9 12 16 21 28
	//1 1 1 1+1 1+1 1+2 1+3 4+1 5+2 7+2 9+3 12+4 16+5 21+7 
	
	int t, n;
	std::cin >> t;
	arr[0] = arr[1] = arr[2] = 1;

	for (int i = 0; i < t; i++) {
		std::cin >> n;

		for (int i = 3; i < n; i++) {
			arr[i] = arr[i - 3] + arr[i - 2];
		}

		std::cout << arr[n - 1] << "\n";

	}

}