백준 2748 C++

호기롭게 DP를 외판원 순회로 풀어보고 벽을 느끼고

다른 문제로 다시 갔을 때 기초가 없는 것 같아서 아예 브론즈 문제부터 풀려고 한다.

 

가장 기초인 피보나치 수열 문제이다.

#include <bits/stdc++.h>

using namespace std;

int n;
long long dp[100];

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> n;

	dp[0] = 0;
	dp[1] = 1;
	dp[2] = 1;

	for (int i = 3; i <= 90; i++) {
		dp[i] = dp[i - 1] + dp[i - 2];
	}

	cout << dp[n];
}

 

#include <bits/stdc++.h>

using namespace std;

int n;
long long dp[100];

long long fibo(int num)
{
	if (num == 1 || num == 2) {
		return 1;
	}
	if (num == 0) {
		return 0;
	}

	if (dp[num] != 0) {
		return dp[num];
	}

	return dp[num] = fibo(num - 1) + fibo(num - 2);
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> n;

	cout << fibo(n);
}