BOJ 9625. BABAA

문제

코드

#include <iostream>

using namespace std;
int a[46], b[46];

int aSum(int x)
{
    a[0] = 0;
    a[1] = 1;
    if (x == 1)
        return 0;

    for (int i = 2; i < x; i++)
    {
        a[i] = a[i - 2] + a[i - 1];
    }

    int res = a[x - 1];

    return res;
}
int bSum(int x)
{
    b[0] = 1;
    b[1] = 1;
    if (x == 1)
        return 1;

    for (int i = 2; i < x; i++)
    {
        b[i] = b[i - 2] + b[i - 1];
    }

    int res = b[x - 1];

    return res;
}
int main(int argc, char const *argv[])
{
    int n;
    cin.tie(NULL);
    ios::sync_with_stdio(false);

    cin >> n;

    cout << aSum(n) << ' ' << bSum(n) << endl;

    return 0;
}

규칙성을 찾아보니 피보나치 수열이 나왔다.
a는 0부터 시작해서 두번째는 1로 시작하는 수열,
b는 1부터 시작하서 두번째도 1로 시작하는 피보나치 수열이다.

각각 a따로 b따로 구해서 입력 숫자에 해당하는 피보나치 수를 출력하는 방법이다.

DP가 어려워서... 가장 기초적인 문제를 시작해보았다.

코드 [(참조 (메모이제이션 이용)]

#include <stdio.h>

int ButtenCheck(int n)
{
    static int mem[45] = {
        1,
        1,
    };
    if (n <= 1)
        return mem[n];
    else if (mem[n] > 0)
        return mem[n];
    return mem[n] = ButtenCheck(n - 1) + ButtenCheck(n - 2);
}
int main()
{
    int K, A, B;
    scanf("%d", &K);
    printf("%d %d", A = ButtenCheck(K - 2), B = ButtenCheck(K - 1));
    return 0;
}