[BOJ] 2748번 : 피보나치 수 2

1. problem : 

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

 

2. solution 1 :

#include <bits/stdc++.h>
using namespace std;
int n;
long long dp[100]; 
long long dynamic_func(int k) {
	if (k == 0 || k == 1) {
		return k;
	}
	if (dp[k]) return dp[k]; 
	return dp[k] = dynamic_func(k-1) + dynamic_func(k-2);
}
int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0); 
	cin >> n; 
	long long ans = dynamic_func(n); 
	cout << ans << '\n';
}

dp를 이용하여, 해결하였다. 단순 재귀를 이용하여 해결할 수 있지만,  단순재귀를 이용하면 틀리도록 출제하도록 한 것 같았다. 

dp에 이미 계산된 결과는 저장해, 다시 한번 계산하는 일이 없도록 코드를 작성했다. 

 

3.  solution 2 :

// Authored by : jihwan0123
// Co-authored by : -
// http://boj.kr/fca58deb2214447782fe6483572acdb8
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll d[100];
int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  d[1] = 1, d[2] = 1;
  for (int i = 3; i <= n; i++)
    d[i] = d[i - 1] + d[i - 2];
  cout << d[n];
}

source code 출처 : https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x10/solutions/2748.cpp

basic-algo-lecture/0x10/solutions/2748.cpp at master · encrypted-def/basic-algo-lecture

이 코드가 훨씬 더 효율적이고, 가독성이 좋았다. dp에 메모만 하면 되기 때문에, 굳이 재귀 말고 반복문으로 처리를 했다.