[ 백준 ] 1737번 - Pibonacci (C++)

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

1737번: Pibonacci

 

 

[ 문제풀이 ]

 

1. dp[ 1001 ][ 320 ]을 선언하고 -1로 초기화해 줍니다.

 

2. P[ i ] = P[ i - 1 ] + P[ i - π * j ]를 통해 dp[ i ][ j ]를 기록해 줍니다.

 

3. 재귀함수를 통해 i - π * j가 0보다 크거나 같고, π보다 작거나 같을 때 1을 return 해줍니다.

 

4. dp[ n ][ 0 ]을 출력합니다.

 

[ 소스코드 ]

#define _USE_MATH_DEFINES
#include<iostream>
#include<cmath>
#define ll long long
#define M 1000000000000000000
 
using namespace std;
 
int n;
ll dp[1001][320];
 
ll dfs(int i, int j)
{
    if (dp[i][j] != -1) return dp[i][j];
    if (i - M_PI * j >= 0 && i - M_PI * j <= M_PI) return 1;
    return dp[i][j] = (dfs(i - 1, j) % M + dfs(i, j + 1) % M) % M;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n;
 
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= 319; j++) {
            dp[i][j] = -1;
        }
    }
 
    cout << dfs(n, 0);
}