baekjoon 2193:이친수

baekjoon 2193 이친수

2193번 이친수

접근

dp(n)을 n자리 이친수 개수라고 한다면
dp(n) = dp(n-2) + … dp(1) + dp(0)이 성립한다.
n자리는 무조건 1, 그럼 n-1자리는 무조건 0
이상태에서 n-2자리부턴 1 또는 0으로 경우가 나뉘는데, 1이면 dp(n-2)이고
0이면 n-3자리로 넘어가서 또 1또는 0으로 나뉜다.

코드

//2193
#include <iostream>
#include <array>
using namespace std;
array<long long int, 91> cache;
long long int dp(int m);
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int n; cin >> n;
  fill(cache.begin(), cache.end(), -1);
  cout << dp(n) << '\n';
  
  
  return 0;
}
long long int dp(int m){
  if(m == 0) return 1;
  if(m == 1) return 1;
  long long int& ret = cache[m];
  if(ret != -1) return ret;
  ret = 0;
  for(int i = 0; i <= m-2; i++){
    ret += dp(i);
  }
  return ret;
}
]

배운 점

기초적인 dp 문제였다.