[백준] 2193번 이친수 C++ 코드

코드

#include <iostream>

using namespace std;
typedef long long ll;

ll n, a[92];

int main() {
  cin >> n;
  a[1] = 1;
  a[2] = 1;
  for(int i = 3; i < n + 1; i++) {
    a[i] = a[i - 1] + a[i - 2];
  }
  cout << a[n] << '\n';
  return 0;
}

풀이

1	1 (1)
2	1 (10)
3	2 (101, 100)
4	3 (1010, 1001, 1000)
5	5 (10101, 10100, 10010, 10000, 10001)
6	8 (101010, 101001,101000,100101,100100,100000,1000001,100010)

피보나치 수열의 규칙을 따르며 증가한다는 것을 확인할 수 있다.