[BOJ][9461] 파도반 수열

Kim Ju Hui·2020년 3월 20일
0

[ 오늘의 문제 한줄평 ]
그놈의 범위

파도반 수열

나름 DP로 알고리즘 잘 짰음

but 더하고 더하고 더하다 보면 int의 범위를 넘어갈 것이라고 상상을 못함(상상도 하지 못한 정체 ㄴㅇㄱ)

그냥 좀 계속 더한다 싶으면 long long 때려 박는게 답인 것인가........
그래도 DP 생각은 했다 뿌듯
왜 문제에서 굳이굳이 P(1)부터 P(10)까지를 주나 했는데 이건 앞에 몇 개를 알아야 풀 수 있는 듯 하다.
어느정도 나선의 형태가 생기기 전 까지는 규칙성이 없다. 물론 P(6)부터는 적용되긴 하는데 P(5)까지는 안된다고 생각한다.

#include <iostream>
#include <cstring>

using namespace std;

int main()
{
    int T, n;
    cin >> T;
    long long P[101];

    while (T--)
    {
        cin >> n;
        memset(P, 0, sizeof(P));

        P[1] = 1;
        P[2] = 1;
        P[3] = 1;
        P[4] = 2;
        P[5] = 2;

        for (int i = 6; i < n + 1;i++)
        {
            P[i] = P[i - 1] + P[i - 5];
        }
        cout << P[n]<<"\n";
    }
}
profile
뻘짓을 많이 하는 꼬부기

0개의 댓글