글 읽기 - DP 이용해서 풀었는데 메모리 초과가 뜨는 이유가 뭘까요????

ther203 5년 전 0

문제에 맞게 DP 테이블이 형성되도록 하여 문제를 풀었는데 메모리 초과가 뜨네요.

재귀함수를 사용한것도 아니고

call by value도 아니고

테이블을 제일 크게 만든다해도 절대 제한 메모리를 초과할 수가 없는 것 같은데 메모리가 초과했다고 하네요.

도움의 손길이 필요합니다.

#include<iostream>
#include<map>
#include<vector>
#include<string>

using namespace std;

long long getNum(int, int);
long long StringToNum(int, vector<int>&);
int minf(int, int);
int maxf(int, int);
long long TenOrder(int N);

int MinCounter = 2;
int MaxCounter = 7;
vector<int> counter = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};

int main() {
	int N = 0;
	long long givenNum;
	vector<int> DigitalNum;
	int flag = 0;
	int orderN = 0;
	int CD = 0;
	int tempCD = 0;	
	long long ans = 0;
	long long orderNum = 1;
	int Num = 0;

	// 입력
	cin >> N;
	DigitalNum = vector<int>(N);
	cin >> givenNum;
	long long temp = givenNum;
	for (int i = 0; i < N; i++) {
		int number = (temp % 10);
		DigitalNum[i] = number;
		temp = temp / 10;
	}

	// 큰 수가 있는지 확인
	for (int i = 0; i < N; i++) {
		Num = DigitalNum[i] + 1;
		CD = CD + counter[Num - 1];
		while (Num < 10) {
			tempCD = CD - counter[Num];
			if (i == 0 && tempCD == 0) {
				flag = 2;
				orderN = i;
				break;
			}

			if (tempCD >= MinCounter*i && tempCD <= MaxCounter*i) {
				flag = 1;
				orderN = i;
				break;
			}

			Num++;
		}

		if (flag > 0) {
			break;
		}

		orderNum *= 10;
	}
	
	// 일의 자리에서 큰 수가 있을 때,
	if (flag == 2) {
		ans = Num;
	}
	// 십의 자리 이상에서 큰 수가 있을 때,
	else if (flag == 1){
		ans = getNum(orderN, tempCD) + Num*orderNum;
	}
	// 큰 수가 전혀 없을 때,
	else {
		ans = getNum(N, CD);
	}
	
	// 답
	cout << (flag > 0?  ans - StringToNum(orderN+1, DigitalNum) : TenOrder(N) - (StringToNum(N, DigitalNum) - ans) );
}

// orderN 자릿수의 수가 tempCD 만큼의 선분을 갖는 가장 작은 숫자를 구함
long long getNum(int orderN, int tempCD) {
	long long tenth = 1;
	map<int, vector<int>> CT;					// counter table
	vector<map<int, long long>> DT(orderN + 1);		// dynamic table for finding number with the given counter: tempCD

	CT.insert(make_pair(0, vector<int>{10}));
	CT.insert(make_pair(1, vector<int>{10}));
	CT.insert(make_pair(2, vector<int>{1}));
	CT.insert(make_pair(3, vector<int>{7}));
	CT.insert(make_pair(4, vector<int>{4}));
	CT.insert(make_pair(5, vector<int>{2, 3, 5}));
	CT.insert(make_pair(6, vector<int>{0, 6, 9}));
	CT.insert(make_pair(7, vector<int>{8}));

	DT[1].insert(make_pair(2, 1));
	DT[1].insert(make_pair(3, 7));
	DT[1].insert(make_pair(4, 4));
	DT[1].insert(make_pair(5, 2));
	DT[1].insert(make_pair(6, 0));
	DT[1].insert(make_pair(7, 8));

	for (int i = 2; i <= orderN; i++) {
		int first = maxf(MinCounter*(i), tempCD - MaxCounter*(orderN - i));
		int last = minf(MaxCounter*(i), tempCD - MinCounter*(orderN - i));
		
		tenth *= 10;
		for (int j = first; j <= last; j++) {
			for (int k = MinCounter; k <= MaxCounter; k++) {
				if( (j-k) >= DT[i-1].begin()->first && (j - k)<= DT[i - 1].rbegin()->first)
					if (DT[i].find(j) == DT[i].end()) {
						DT[i].insert(make_pair(j, DT[i - 1][j - k] + tenth * CT[k][0]));
					}
					else {
						if (DT[i][j] > DT[i - 1][j - k] + tenth*CT[k][0]) {
							DT[i][j] = DT[i - 1][j - k] + tenth*CT[k][0];
						}
					}
			}
		}
				
	}

	return DT[orderN][tempCD];
}

long long StringToNum(int orderN, vector<int>& DigitalNum) {
	long long ans = 0;
	long long order = 1;

	for (int i = 0; i < orderN; i++) {
		long long num = DigitalNum[i]*order;
		ans = ans + num;
		order *= 10;
	}

	return ans;
}

int minf(int a, int b) {
	return (a < b ? a: b);
}

int maxf(int a, int b) {
	return (a > b ? a : b);
}

long long TenOrder(int N) {
	long long ans = 1;
	for (int i = 0; i < N; i++) {
		ans *= 10;
	}

	return ans;
}

djm03178 5년 전 1

31번째 줄은 왜 있는 건가요? N이라는 건 주어지지 않습니다.

ther203 5년 전 0

자릿수 입력받으려고 한겁니다.

djm03178 5년 전 1

N은 입력으로 주어지지 않습니다. 입력으로 들어오는 문자열의 길이가 N이라는 것입니다.

ther203 5년 전 0

아!!!!!! 감사합니다.... ㅜㅜㅜㅜㅜㅜㅜ

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

문제

문제

출처

ICPC

DP 이용해서 풀었는데 메모리 초과가 뜨는 이유가 뭘까요????

ther203 5년 전 0

djm03178 5년 전 1

ther203 5년 전 0

djm03178 5년 전 1

ther203 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말