[9461번] 파도반 수열

www.acmicpc.net/problem/9461

9461번: 파도반 수열

 

위 그림과 같은 나선 모양의 정삼각형들을 연속적으로 그려나갈때

입력받은 N번째에 해당하는 정삼각형의 변 길이를 구하는 문제이다.

 

정삼각형의 변의 길이 P(N)을 나열해 보면 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, ... 이다.

 

첫번째 원소부터 살펴보면 규칙성이 잘 보이지 않는다.

하지만 여섯번째 원소(3)부터는 직전의 원소(2)와 5칸 앞의 원소(1)의 합이라는 규칙성을 찾을 수 있다.

 

• 일곱번째 원소(4) = 직전 원소(3) + 5칸 앞의 원소(1)
• 여덟번째 원소(5) = 직전 원소(4) + 5칸 앞의 원소(1)
• 일곱번째 원소(7) = 직전 원소(5) + 5칸 앞의 원소(2)
• 여덟번째 원소(9) = 직전 원소(7) + 5칸 앞의 원소(2) 
• 일곱번째 원소(12) = 직전 원소(9) + 5칸 앞의 원소(3)
• 여덟번째 원소(16) = 직전 원소(12) + 5칸 앞의 원소(4)
• 일곱번째 원소(21) = 직전 원소(16) + 5칸 앞의 원소(5)

 

따라서 이를 점화식으로 나타내면 다음과 같다.

 

i 가 6 보다 작을 때는 기존의 p배열을 통해 미리 입력 해둔 값을 dp 테이블에 저장하고

나머지 경우에는 직전원소와 5칸 앞의 원소를 합한 값을 저장한다.

 

추가적으로 n은 최대 64로, int형으로 선언된 dp 테이블에서 오버플로우가 발생하게 되기 때문에

dp 테이블을 long long으로 선언해줘야한다.

 

전체코드

전체코드

#include <iostream>

using namespace std;

int main() {

	int t; cin >> t;

	long long p[7] = { 0,1,1,1,2,2,3 };

	while (t--) {

		int n; cin >> n;
		long long dp[101] = {0, };

		for (int i = 1; i <= n; i++) {
			if (i <= 6) {
				dp[i] = p[i];
			}
			else {
				dp[i] = dp[i - 1] + dp[i - 5];
			}
		}

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

	}

}