백준 9461번 파도반 수열

문제 링크입니다: https://www.acmicpc.net/problem/9461

상당히 쉬운 문제였습니다.

규칙이 명확하기 때문에 적절히 재귀를 이용해주면 됩니다.

/*

첫 삼각형은 정삼각형으로 변의 길이는 1이다.

그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다.

나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다.

 

파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다.

P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다.

 

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

*/

#include <iostream>

#include <cstring> //memset

using namespace std;

 

int N;

long long cache[101]; //최대 100

 

void initialize(void) //cache 초기화

{

        cache[1] = cache[2] = cache[3] = 1;

}

 

long long length(int N)

{

        long long &result = cache[N];

        if (result != -1)

               return result;

        return result = length(N - 2) + length(N - 3);

}

 

int main(void)

{

        int test_case;

        cin >> test_case;

 

        memset(cache, -1, sizeof(cache)); //cache는 한번만 초기화해야지 속도향상에 도움이 된다

        initialize(); //초기화

        for (int i = 0; i < test_case; i++)

        {

               cin >> N;

               cout << length(N) << endl;

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~