[DP] 파도반 수열 Padovan sequence

파도반 수열

Padovan sequence

---

 

1, 1, 1, 2, 2, 3, 4, 5, 7, 9...

 

 

위 그림과 수열로 구성된 문제가 국내 ACM 문제 중 하나로 나왔었습니다.

그림, 수열을 참고하여 정수 n을 입력했을 때 n번째 값을 출력하는 내용입니다.

수열의 초기값과 점화식을 알고 있으면 아아아주 쉽게 풀 수 있지만 그림과 수열로 유추하실 수 있으면 더 좋겠습니다!

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

파도반 수열이란??

---

Richard Padovan에 의해 이름붙었습니다.

위 그림은 파도반 수열을 표현하는 그림 중 하나입니다.

각 삼각형은 한 변을 두 개의 다른 삼각형과 공유하는데요, 초기값 P(0)~P(2)를 제외하고 P(n) = P(n-2) + P(n-3)임을 알 수 있습니다.

 

* 초기값이 P(0) = P(1) = P(2) = 1인 정수 P(n)의 나열이다.

 

* 이후의 값은 P(n) = P(n-2) + P(n-3)으로 나타낸다.

 

 

 

n = 0, 1,...에 해당하는 파도반 수열은 아래와 같다.

1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37, 49, 65, 86, 114, 151, 200, 265

 

 

 

 

 

 

 

 

 

 

 

 

 

 

저의.. 볼거없는 코드

---

#include <iostream>
using namespace std;
long long P_arr[100] = { 0 };
long long P(int n){
	P_arr[0] = 1; P_arr[1] = 1; P_arr[2] = 1;

	if (n < 3) return P_arr[n];
	else{
		if (P_arr[n] == 0){
			P_arr[n] = P(n-2) + P(n - 3);
		}

		return P_arr[n];
	}

}
int main() {

	int n;
	while (true){
		cout << "파도반 수열의 n번째 숫자를 출력합니다.. n을 입력하세요: ";
		cin >> n;
		cout << P(n) << endl<<endl;
	}
	return 0;
}

 

결과

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

파스칼의 삼각형에서??

---

 

Erv Wilson이 발견한 바에 따르면, 파스칼의 삼각형에서 위 그림과 같이 대각선으로 숫자들을 더할 때 파도반 수열이 나타난다.

그는 1993년에 이러한 그림을 그렸는데 이 때는 사실 아직 파도반 수열이 발견되기 1년 전이었다.

2016년에 Tony Foster가 위와 같은 그림이 파도반 수열과 관련있다고 정의했다.

 

-

https://en.wikipedia.org/wiki/Padovan_sequence