[Algorithm] Baekjoon 9461번 : 파도반 수열

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

9461번: 파도반 수열

vector<int> results;
long long p[101] = { 0 };
int maxNum = 6;
 
 
void solve(int n)
{
    int result = 0;
 
    if (n > maxNum)
    {
        for (int i = maxNum+1; i <= n; i++)
        {
            p[i] = p[i - 1] + p[i - 5];
        }
 
        maxNum = n;
    }
    
    cout << p[n] << endl;
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int t = 2;
    int input = 0;
 
    p[0] = 0;
    p[1] = 1;
    p[2] = 1;
    p[3] = 1;
    p[4] = 2;
    p[5] = 2;
    p[6] = 3;
 
    cin >> t;
 
    for (int i = 0; i < t; i++)
    {
        cin >> input;
        solve(input);
    }
}

 

규칙은 빨리 찾았는데, 배열 데이터타입을 크게 안잡아놔서 헤맨 문제다.

그림보면 i번째의 새로운 삼각형의 변의 길이는, i-1번째와 i-5번째 삼각형변의 길이를 더한것과 일치하단걸 알 수 있다.

나는 바보같이 배열을 int로 너무 작게 잡아놨어서.. 

어쨌든 규칙찾는건 어렵지 않다.