[알고리즘] 파도반수열 (bk_9461)

문제

오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다.

파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다.

N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오.

규칙성 찾기

1
1
1
2
2
1 + 2 = 3 (1, 5)
1 + 3 = 4 (2, 6)
1 + 4 = 5 (3, 7)
2 + 5 = 7 (4, 8)
2 + 7 = 9 (5, 9)
3 + 9 = 12(6, 10)

생각한 알고리즘

• 6번째 수열부터는 a_n = a_(n-1) + a_(n-5)를 따른다.
• 다음 점화식을 이용하여 프로그램을 작성한다.

#include <iostream>

using namespace std;

int main(void)
{
    int count;
    cin>>count;
    int input[110];
    for(int i = 0; i< count; i++)
    {
        cin>>input[i];
    }

    long int arr[110];
    arr[1] = 1;
    arr[2] = 1;
    arr[3] = 1;
    arr[4] = 2;
    arr[5] = 2;
    int fill = 6;

    for(int i = 0; i <count; i++)
    {

        while(fill <= input[i])
        {
            arr[fill] = arr[fill-1] + arr[fill-5];
            fill += 1;
        }
        cout<<arr[input[i]]<<endl;
    }
    return 0;

}