글 읽기 - [10844] 메모리 초과 C++ 질문입니다.

kk0640 3년 전 0

재귀함수를 통해서 풀었고 모든 타입 long long으로 바꾸고 mod도 매 번 해주었는데 어째서 메모리 초과가 나는 것일까요?

#include <iostream>
#define mod 1000000000
using namespace std;

long long dp[101][11];

void init_()
{

    for (int i = 0; i < 102; i++)
    {
        for (int j = 0; j < 10; j++)
        {
            dp[i][j] = -1;
        }
    }

    dp[1][0] = 0;
    for (int i = 1; i <= 9; i++)
    {
        dp[1][i] = 1;
    }
    dp[2][0] = 1;
    dp[2][1] = 1;
    for (int i = 2; i <= 8; i++)
    {
        dp[2][i] = 2;
    }
    dp[2][9] = 1;
}

long long solve(int N, int idx)
{

    long long& ret = dp[N][idx];

    if (ret != -1)
    {
        return ret;
    }

    if (idx == 0)
    {
        dp[N][idx] = solve(N-1,idx+1) % mod;
    }
    else if (idx == 9)
    {
        dp[N][idx] = solve(N - 1, idx - 1) % mod;
    }
    else
    {
        dp[N][idx] = (solve(N - 1, idx - 1)%mod + solve(N + 1, idx + 1)%mod);
    }

    return dp[N][idx];
}


int main()
{
    int n = 0;
    long long ans = 0;

    cin >> n;
    init_();
    for (int i = 0; i < 10; i++)
    {
        ans = (ans+ solve(n, i))%mod;
    }

    cout << (ans % mod) << endl;

    return 0;
}

wrath9764 3년 전 2

solve의 else문에서 N을 증가시키셨네요

kk0640 3년 전 0

감사합니다.

적게 일하고 많이 버시길 기도드리겠습니다..

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[10844] 메모리 초과 C++ 질문입니다.

kk0640 3년 전 0

wrath9764 3년 전 2

kk0640 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말