본문으로 바로가기

길이가 n인 이친수는 마지막 자리수가 0일 경우 (n-1)자리가 이친수이면 되고 마지막 자리수가 1일 경우 (n-1)자리가 반드시 0이고 (n-2)가 이친수인 경우가 있다.

#include <cstdio>

typedef long long ll;

ll dp[91];
int n;

ll f(int);// 길이가 n인 이친수의 개수

int main() {
  scanf("%d", &n);
  printf("%lld\n", f(n));
  return 0;
}

ll f(int n) {
  if (n == 1) return 1;
  if (n == 2) return 1;
  if (dp[n]) return dp[n];

  // 길이가 n인 이친수는 마지막 자리수가 0일 경우 (n-1)자리가 이친수이면 되고
  // 마지막 자리수가 1일 경우 (n-1)자리가 반드시 0이고 (n-2)가 이친수인 경우가 있다
  return dp[n] = f(n-1) + f(n-2);
}

'Programming > Baekjoon Online Judge' 카테고리의 다른 글

[BOJ] 2156: 포도주 시식  (0) 2018.05.15
[BOJ] 9465: 스티커  (0) 2018.05.15
[BOJ] 2193: 이친수  (0) 2018.05.15
[BOJ] 11057: 오르막 수  (0) 2018.05.15
[BOJ] 10844: 쉬운 계단 수  (0) 2018.05.15
[BOJ] 11052: 붕어빵 판매하기  (0) 2018.05.15

댓글을 달아 주세요