(24416) 알고리즘 수업 - 피보나치 수 1

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

단계별로 풀어보기

21단계(동적 계획법 1) 1번째

 

 

 

드디어 대망의 동적 계획법 단계. 워낙 폭넓고 유명한 분야라 개념 설명은 생략한다.

피보나치 재귀 코드는 이미 재귀 단계에서 익혀봤으니 구현 없이 바로 풀었다. 코드1 실행 횟수는 n번째 피보나치 수와 같다.

 

 

 

#include <iostream>
using namespace std;

int main() 
{
  int n;
  
  cin >> n;
  
  pair<int, int> p= {1, 1};
  
  for(int i=2;i<n;i++)  p= {p.second, p.first+p.second};
  
  cout << p.second << " " << n-2;
  
  return 0;
}