[알고리즘] 무한 수열

https://www.acmicpc.net/problem/1351

#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>

#define MAX_MEMO_SIZE 1000

typedef struct memo_entry_s memo_entry_t;
struct memo_entry_s {
    int64_t key;
    int64_t value;
};

int64_t
find_in_memo(memo_entry_t *memo, size_t size, int64_t key) {
    for (size_t i = 0; i < size; i++) {
        if (memo[i].key == key) {
            return memo[i].value;
        }
    }
    return -1;
}

void
add_to_memo(memo_entry_t *memo, size_t *size, int64_t key, int64_t value)
{
    memo[*size].key = key;
    memo[*size].value = value;
    (*size)++;
}

int64_t
find_An_recursively(int64_t N, int64_t P, int64_t Q, memo_entry_t *memo, size_t *size)
{
    int64_t result = find_in_memo(memo, *size, N);
    if (result != -1) {
        return result;
    }
    result = find_An_recursively(N / P, P, Q, memo, size) + find_An_recursively(N / Q, P, Q, memo, size);
    add_to_memo(memo, size, N, result);
    return result;
}

int
main()
{
    int64_t N;
    int64_t P;
    int64_t Q;

    memo_entry_t memo[MAX_MEMO_SIZE];
    memo[0].key = 0;
    memo[0].value = 1;
    size_t size = 1;

    scanf("%" SCNd64 " %" SCNd64 " %" SCNd64, &N, &P, &Q);
    printf("%" PRId64 "\n", find_An_recursively(N, P, Q, memo, &size));

    return 0;
}

나의 풀이

- find_An_recursively 함수에서 N, P, Q의 type을 int64_t로 안하고 int로 두고 있었다.

- 계속 틀렸다.

- 타입명을 잘 확인하자!