[C] 백준 | 9625번 코드 - BABBA

>문제

www.acmicpc.net/problem/9625

9625번: BABBA

> 핵심

피보나치 수열

DP

>풀이과정

DP 문제라길래 DP스럽게 풀어보려고 했다. 맞게 푸는건지 모르겠네

메모이제이션을 하기 위한 배열을 int형이 아니라 구조체 배열로 만들어서 A와 B의 개수를 따로따로 세기 편하도록 했다.

꼭 구조체가 아니더라도 A, B 두가지 경우밖에 없기 때문에 이차원배열을 통해서 구분해도 될 것 같다.

 

크게 어렵지는 않았다!

>깨달은점

모르겠다

BABA!

>코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

#define SIZE 46

typedef struct
{
    int cnt_A;
    int cnt_B;
}node;

node dp[SIZE];

void init_dp()
{
    for (int i = 0; i < SIZE; i++)
    {
        dp[i].cnt_A = 0;
        dp[i].cnt_B = 0;
    }
}

node dynamic(int n)
{
    if (n == 0)
    {
        node tmp;
        tmp.cnt_A = 1; 
        tmp.cnt_B = 0;
        return tmp;
    }
    if (n == 1)
    {
        node tmp;
        tmp.cnt_B = 1;
        tmp.cnt_A = 0;
        return tmp;
    }
    if (dp[n].cnt_A != 0 || dp[n].cnt_B != 0) return dp[n];

    node tmp_1, tmp_2;
    tmp_1 = dynamic(n - 1);
    tmp_2 = dynamic(n - 2);

    dp[n].cnt_A = tmp_1.cnt_A + tmp_2.cnt_A;
    dp[n].cnt_B = tmp_1.cnt_B + tmp_2.cnt_B;

    return dp[n];
}


int main()
{
    int n, m;
    node tmp;

    scanf("%d", &n);
    tmp = dynamic(n);

    printf("%d %d\n", tmp.cnt_A, tmp.cnt_B);

    return 0;
}