백준 1737번, Pibonacci 풀이

문제

백준 1737번

풀이

기본적인 피보나치 문제도 DP이기 때문에, DP를 사용하는 문제임에는 쉽게 알 수 있습니다.

다만, 소수점 오차 때문에 dp table을 잡기가 조금 애매합니다.

 

소수점 오차를 줄이기 위해서 $ n $에서 뺄 1의 개수와 $ \pi $의 개수를 기록하여 dp table을 채우면 될 것 같습니다.

 

$ dp[i][j] = f(n - i - \pi j) $라고 두고 재귀 함수로 풀었습니다. (단, $ f $는 Pibonacci 함수)

소스코드

#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ull;

ull MOD = 1000000000000000000;

ull dp[1001][1001];
long double n;

ull solve(int i, int j) {
	long double curr = n - 1 * i - M_PI * (long double)j;
	if (0 <= curr && curr <= M_PI) return 1;
	else if (curr < 0) return 0;

	if (dp[i][j]) return dp[i][j];

	return dp[i][j] = (solve(i + 1, j) + solve(i, j + 1)) % MOD;
}

int main() {
	cin >> n;
	cout << solve(0, 0);
}