글 읽기 - 왜 메모리 초과인지 알려주세요 ㅠ

blackpoplar1004 1년 전 0

왜 메모리 초과인지 알고 싶습니다..

#include <iostream>
#include <vector>
using namespace std;
#define INF 1'000'000'000
#define MAX 500

// 크기가 N×M인 행렬 A와 M×K인 B를 곱할 때 필요한 곱셈 연산의 수는 총 N×M×K
// 곱셉의 연산 횟수의 최솟값을 구하라!
int dp[MAX][MAX]; // 행렬 A, 행렬 B -> dp[A][B] 곱셉 연산의 최솟값.
int matirx[MAX][2];

int dynamicDP(int r, int c)
{
    if(dp[r][c] > 0) return dp[r][c]; 

    if(c - r <= 0) return 0;

    int maxmin = INF; 

    for(int k = r; k <= c; ++k)
    {
        maxmin = min(maxmin, dynamicDP(r, k) + dynamicDP(k + 1, c) 
        + (matirx[r][0] * matirx[k][1] * matirx[c][1]));
    }

    return dp[r][c] = maxmin;
}

int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int N; //행렬의 개수 N (1 ≤ N ≤ 500)
    cin >> N; 

    for (int i = 0; i < N; ++i)
    {
        // 행렬의 크기 (1 ≤ r, c ≤ 500)
        // 항상 순서대로 곱셈을 할 수 있는 크기만 입력
        cin >> matirx[i][0] >> matirx[i][1];
    }

    cout << dynamicDP(0, N-1);

    return 0;
}

djm03178 1년 전 0

N이 500일 때 dynamicDP(x,499) 함수가 dynamicDP(500,499)를 호출하게 되면서 14번째 줄에서 존재하지 않는 dp[500][499]에 접근하게 됩니다.

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

문제

문제

출처

ICPC

왜 메모리 초과인지 알려주세요 ㅠ

blackpoplar1004 1년 전 0

djm03178 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말