문제링크 

 

DP 메모이제이션으로 풀 수 있었다. 

n번째 피보나치 수를  출력하면 된다. 

수의 크기 n이 크지않아서 long long 배열로 충분했다. 

 

 

"맞았습니다." 코드 

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

long long D[47];
int n;

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> n;

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

  cout << D[n];
  return 0;
}

 

728x90

백준 2749번 피보나치 수 3

 
 
백준 9471번 피사노주기 문제를 읽어보면, 피사노 주기의 내용을 설명하고 있다. 
주기의 길이가 p이면, 
n번째 피보나치 수를 m으로 나눈 나머지는 n%p번째 피보나치 수를 m으로 나눈 나머지와 같다. 
 
피보나치 수 3 문제에서 m은 10의 6승으로 주어졌다. 
n번째 피보나치 수를 10의 6승으로 나눈 나머지는 n%p번째 피보나치 수를 10의 6승으로 나눈 나머지와 같다. 
 
#include <bits/stdc++.h>
using namespace std;

long long n, cnt;
vector<int> v;

void pisano(int m){
  v.push_back(0); // 0번째 피보나치 수
  v.push_back(1); // 1번째 피보나치 수
  v.push_back(1); // 2번째 피보나치 수

  cnt = 2; // 3번째 피보나치 수를 구하기 위해 2번째와 1을 연산해야 한다.

  while(1){
    v.push_back((v[cnt] + v[cnt-1]) % m);
    cnt++;
    if(v[cnt] == 0 && v[cnt-1] == 1) break; // 주기를 구한 순간.
  }

}

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> n;

  pisano(1000000);
  cout << v[n % cnt];

  return 0;
}
 



참고
728x90

'알고리즘 > 백준' 카테고리의 다른 글

피보나치 수 5 백준 10870번 c++  (0) 2022.02.08
피보나치 수 백준 2747번 c++  (0) 2022.02.08
피사노 주기 백준 9471 c++  (0) 2022.02.08
1로 만들기2 백준 12852 c++  (0) 2022.02.04
피보나치 수2 백준 2748 c++  (0) 2022.02.04

+ Recent posts