[BOJ] 1788번 : 피보나치 수의 확장

1. problem : 

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

 

2. solution 1 :

#include <bits/stdc++.h>
using namespace std;

int n;
const int mod = 1000000000;
const int val = 1000005;
int d[val]; 

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n; 
	d[1] = 1; 
	for (int i = 2; i <= abs(n); i++) d[i] = (d[i - 1] % mod + d[i - 2] % mod) % mod;
	if (n < 0) {
		if (abs(n) % 2 == 0) {
			cout << -1 << '\n';
		}
		else cout << 1 << '\n';
	}
	else {
		if (n == 0) cout << 0 << '\n';
		else cout << 1 << '\n';
	}
	cout << d[abs(n)] << "\n";
}

dp를 이용해 풀었다. 따라서, 세 가지 스텝을 따른다. 

1. 테이블을 정의한다. d[i] = i번째 피보나치 수 

2. 점화식을 작성한다. d[i] = d [i-1] + d [i-2]  

3. 초기값을 설정한다. d[0] = 0, d [1] = 1

n이 음수일 경우는 -1 과 1 출력만 구분해 주면 된다. 

 

3. solution 2 :

// Authored by : Hot6Mania
// Co-authored by : -
// http://boj.kr/d9e1409ef9b5495cb1cb818ff94d9203
#include <bits/stdc++.h>
using namespace std;

int n;
int d[1000010];
int mod = 1e9;

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  
  cin >> n;
  d[0] = 0; d[1] = 1;
  if(n >= 0){
    for(int i = 2; i <= n; ++i)
      d[i] = (d[i-1] + d[i-2]) % mod;
  }
  else{
    n = abs(n);
    for(int i = 2; i <= n; ++i)
      d[i] = (d[i-2] - d[i-1]) % mod;
  }
  if(d[n] > 0) cout << "1\n";
  else if(d[n] < 0) cout << "-1\n";
  else cout << "0\n";
  cout << abs(d[n]);
}

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

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