백준 9461 파도반 수열

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

문제와 채점은 위 사이트에서 확인 하실 수 있습니다

 

이 문제는 삼각형이 나선형으로 놓여집니다. 이때 나선에서 가장 긴변의 길이를 k라고 하고 k길이의 정삼각형을 추가하는 방식으로 배치가 되는데

 

N번째 진행시 k의 값을 구하는 문제입니다.

 

수열을 쭉 보시면 1 1 1 2 2 3 4 5 7 9 12 ... 으로 진행되는데 n번째 값은 n-1과 n-5를 더하면 나온다는 것을 알 수 있습니다.

 

따라서 그에따라 점화식을 세워주면 풀리는 문제입니다. 주의할점은 n이 100까지 가능하므로 오버플로우가 일어날 수 있어 longlong형으로 선언 해주셔야 합니다.

 

다음은 코드입니다. 

 

 #include <iostream>

using namespace std;

int main(void) {
	int T; cin >> T;
	long long dp[101] = {0, };
	dp[1] = 1;
	dp[2] = 1;
	dp[3] = 1;
	dp[4] = 2;
	dp[5] = 2;
	for(int i = 6; i <= 100; i++)
		dp[i] = dp[i-1] + dp[i-5];

	while(T--) {
		int N; cin >> N;
		cout<<dp[N]<<'\n';
	}	
}