BOJ 9461 파도반 수열

문제출처 : https://www.acmicpc.net/problem/9461

1. 문제요약

- 아래 그림처럼 정삼각형을 이어붙임

- 해당 나선 그림에서 가장 긴 변의 길이를 k라 했을 떄, 그 변에 길이가 k인 정삼각형을 추가

- 파도반 수열 p[n]은 나선에 있는 정삼각형의 한 변의 길이

  p[1] ~ p[10]까지 1, 1, 1, 2, 2, 3, 4, 5, 7, 9

- 1 <= n <= 100일때 p[n]의 값은?

2. 접근방법

- 수열의 규칙 찾기

- p[n] = p[n-1] + p[n-5]

3. 시간복잡도

- n

4. 회고

- p[n]의 값이 int 범위를 넘어감.

- 가장 작은 입력, 가장 큰 입력에 대해 테스트 필요함

소스코드

#include<iostream>
using namespace std;

int t, n;
long long p[101] = { 0, 1, 1, 1, 2, 2 };

int main(void){
	for (int i = 6; i < 101; i++)
		p[i] = p[i - 1] + p[i - 5];
	cin >> t;
	while (t--){
		cin >> n;
		cout << p[n] << "\n";
	}
	return 0;
}

[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]