글 읽기 - 메모리 초과가 왜 일어날까요 ㅠㅠ

kim031504 4년 전 0

2차원 배열을 동적할당하여

동적 프로그래밍으로 접근하였습니다.

하지만 메모리 초과가 나네요... ㅠ

혹시 이것에 관한 해결책이 있을까요...?

자세한 코드 설명은 주석으로 처리하였습니다!

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
	int n, k;

	cin >> n >> k;

	int *Coin = new int[n];

	for (int i = 0; i < n; i++)
	{
		int num;
		cin >> num;

		Coin[i] = num;
	}

	// 동전의 가치는 먼저 오름차순 정렬을 하고서 접근한다.
	sort(Coin, Coin + n);


	// 경우의 수가 많을 경우를 대비하여 큰 자료형으로 2차원 배열 동적할당!
	unsigned long **DP = new unsigned long*[n];


	// n * k 의 2차원 배열이 만들어진다.
	for (int i = 0; i <n; i++)
	{
		DP[i] = new unsigned long[k + 1];
	}


	// 일단 모두 0으로 초기화
	for (int i = 0; i < n; i++)
	{
		for (int j = 1; j <= k; j++)
		{
			DP[i][j] = 0;
		}
	}



	for (int i = 0; i < n; i++)
	{

		// 만일 첫 코인이라면
		// 그의 배수가 되는 것만 경우의 수 1로 만든다.
		if (i == 0)
		{
			for (int j = Coin[i]; j <= k; j++)
			{
				if (j%Coin[i] == 0)
				{
					DP[i][j] += 1;
				}
			}

			continue;

		}

		// 첫 코인이 아니라면 다음을 시행한다.
		for (int j = 1; j <= k; j++)
		{

			// 해당 코인보다 작은 값이라면 이 코인으로 만들 수 있는 가치가 아니므로
			if (j<Coin[i])
			{
				// 이전 값으로 대입
				DP[i][j] = DP[i-1][j];
			}

			// 코인의 값과 같은 가치라면 이전 코인까지 구한 것이 이 코인 하나로 만드는거니까
			else if (j == Coin[i])
			{
				// 플라스 1
				DP[i][j] = DP[i - 1][j] + 1;
			}

			// 나머지 경우에는 점화식을 통해 푼다!
			else
			{
				DP[i][j] = DP[i][j - Coin[i]] + DP[i-1][j];
			}
		}
	}

	// 출력!
	cout << DP[n-1][k] << endl;

	return 0;

}

djm03178 4년 전 1

한 번 DP에 할당되는 메모리 크기가 얼마가 되는지 직접 계산해보세요.

kim031504 4년 전 0

2차원 -> 1차원으로 바꾸니까 정답이네요!

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

문제

문제

출처

ICPC

메모리 초과가 왜 일어날까요 ㅠㅠ

kim031504 4년 전 0

djm03178 4년 전 1

kim031504 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말