[백준] 9461 파도반수열 (C++)

 

문제 URL:

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

9461번: 파도반 수열

 

다음 문제는 숫자 N이 주어졌을 때, 나선에 있는 정삼각형의 변의 길이인 파도반 수열 P(N)을 구하는 문제이다. 

이 문제를 처음 봤을 때 파도반 수열의 규칙이 존재한다고 예상할 수 있었는데 그 규칙을 찾기까지 시간이 걸렸다.

 

 

다음 그림을 언뜻 보면,

 

P(1) = 1

P(2) = 1

P(3) = 1

P(4) = 2로

4번째 삼각형부터 DP[i] = DP[i-3] + DP[i-1]과 같은 규칙을 이루는 것처럼 보이지만

그 다음 삼각형을 보면 P(5) = 2이므로 다음이 성립되지 않음을 알 수 있다. 

 

 

규칙을 찾기 위해 삼각형을 더 살펴보았는데,

 

P(6) = 3

P(7) = 4

P(8) = 5

P(9) = 7

...

이렇게 6번째 삼각형부터 DP[i] = DP[i-5] + DP[i-1]과 같은 규칙을 이루는 걸 찾아볼 수 있었다.

따라서 코드는 다음과 같다. 

---

#include <iostream>
#define MAX 110
using namespace std;

int N; 
long long dp[MAX];

void solution() {
	dp[1] = dp[2] = dp[3] = 1;
	dp[4] = dp[5] = 2;

	for (int i = 6; i <= N; i++)
		dp[i] = dp[i - 1] + dp[i - 5];

	cout << dp[N] << '\n';
}

int main() {
	int T;
	cin >> T;

	for (int i = 0; i < T; i++) {
		cin >> N;
		solution();
	}
}