[백준][C++]9461번. 파도반 수열

https://www.acmicpc.net/problem/9461

 

이 문제는 규칙을 찾아서 점화식으로 만들고 매번 n번째까지 계산을 하면 시간 초과가 뜨기 때문에 미리 100개를 계산해두고 필요한 부분만 꺼내 쓰게 구현하면 된다. 

이때 규칙은 그림을 보면 n-2번째하고 n-3번째 삼각형의 한변의 길이를 더하면 n번째 삼각형의 한변의 길이가 되는 것을 볼 수 있다. 이때 100번째 까지 가다보면 값이 커질 수 있기 때문에 long배열을 사용하자

 

정답코드

#include <iostream>

using namespace std;

int main()
{
    int t;

    cin >> t;

    long p[101] = { 0 };

    p[1] = p[2] = p[3] = 1;

    // 배열 미리 계산 
    for (int i = 4; i <= 100; i++) {
        p[i] = p[i - 2] + p[i - 3];
    }

    for (int i = 0; i < t; i++) {
        int n;
        cin >> n;
        cout << p[n] << endl;
    }

    return 0;
}