글 읽기 - 메모리 초과 관련

sarna 7년 전 0

자꾸 메모리 초과가 나서 이런저런 방법을 써봐도 모두 안되네요. 재귀점화식으로 푸는 건 아닌 것같고 메모이제이션 말고 다른 푸는 방법이 있나요? 아니면 혹시 그냥 제 코드가 잘못된걸까요?

#include <iostream>

using namespace std;

class binomialCoefficient {
public:
	binomialCoefficient(int n, int k) :N(n), K(k) {
		binomialArray = new int*[n + 1];

		for (int i = 0; i < n + 1; i++) {
			binomialArray[i] = new int[i + 1];
		}

		for (int i = 0; i < n + 1; i++) {
			for (int j = 0; j < i + 1; j++) {
				binomialArray[i][j] = 0;
			}
		}

	}
	~binomialCoefficient() {
		delete[] binomialArray;
	}
	int computeBinomial(int n, int k) const {
		int i, j;

		for (i = 0; i <= n; i++) {
			for (j = 0; j < i + 1; j++) {
				if (j == 0 || j == i)
					binomialArray[i][j] = 1;
				else
					binomialArray[i][j] = binomialArray[i - 1][j - 1] + binomialArray[i - 1][j];

			}
		}
		return binomialArray[n][k];
	}
	void printBinomial() const {
		cout << computeBinomial(N, K) << endl;
	}
private:
	int N;
	int K;
	int** binomialArray;
};

int main()
{
	int N, K;

	while (true) {
		cin >> N >> K;

		if (N == 0 && K == 0)
			break;

		binomialCoefficient* bi = new binomialCoefficient(N,K);

		bi->printBinomial();
		delete bi;
	}

	return 0;
}

chogahui05 7년 전 2

n개 중 1개를 택하는 경우가 int형 범위 내에 들어오는 경우.

n의 범위는 1<=n<=2147483647이네요.

n개 중 2개를 택하는 경우가 int형 범위에 들어오는 경우

n의 범위는 n(n-1)/2 <= 2^31 - 1이니까, 2147483647보다는 훨씬 줄어들겠지만, 여전히 dp를 사용해서 풀기는 어렵습니다.

nCm을 전개해 보세요. 이게 힌트가 될 수 있을 거 같네요.

sarna 7년 전 0

좋은 말씀 감사합니다. 가르쳐주신 점 다시 배워 풀어보도록 하겠습니다

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

문제

문제

출처

ICPC

메모리 초과 관련

sarna 7년 전 0

chogahui05 7년 전 2

sarna 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말