[BOJ] 9461 파도반 수열

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

9461번: 파도반 수열

---------------------------------------------------핵심 알고리즘--------------------------------------------

 

수학(규칙찾기) + dp

 

---------------------------------------------------풀이----------------------------------------------------

 

삼각형을 살펴보면 규칙을 찾을 수 있는데, 5번째 이전 삼각형과 바로 이전 삼각형의 변으로 새로운 삼각형이 만들어진다는 것이다.

따라서, 이 삼각형의 한 변의 값들을 저장할 Pn[] 배열을 만들어

find_Pn() 함수에서 Pn[n]이 이미 존재하면 그 값을,

아니라면 find_Pn(n-5) + find_Pn(n-1)을 Pn[n]에 저장하며 리턴하도록 하였다.

#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <stack>
#include <limits.h>
#include <map>

using namespace std;

long long Pn[101] = {0, };

long long find_Pn(int n){
    if(Pn[n] > 0){
        return Pn[n];
    }
    return Pn[n] = find_Pn(n-5) + find_Pn(n-1);
}

int main(void){
    FASTIO;
    int T;
    cin >> T;
    Pn[1] = Pn[2] = Pn[3] = 1;
    Pn[4] = Pn[5] = 2;
    while(T--){
        int N;
        cin >> N;
        cout << find_Pn(N) << "\n";
    }
    return 0;
}

 

---------------------------------------------------후기----------------------------------------------------

 

간단한 dp 문제.

그런데 바로 틀렸다가 떠서 당황했다. N을 100을 넣어보니 int 범위를 초과해 마이너스 값이 뜨더라,,:(

long long으로 바꿔주니 해결되었다.

이런 int 범위 넘어가서 문제 생기는 문제들 너무 싫다...