글 읽기 - 메모리 초과가 뜨는데 혹시 개선방안이 있을까요..

o9j8w7 1년 전 0

제 코드가 좀 난잡하긴합니다..

대충 구현방향은 우선 20이하의 숫자에 대해서는 앞의 dp를 통해서 답을 출력합니다.

그 후 큰 수들에 대한 처리를 dp3 에서 담당해서 처리합니다.

혹시 dp3 크기 때문에 메모리초과가 나는 걸까요? 고수분들 도와주시면 정말 감사하겠습니다..

#include<iostream>
#include<string>
#include<map>
#include<algorithm>
#include<vector>
#include<sstream>
#include<stack>
#include<queue>
#include<cmath>

using namespace std;

int power(int a, int b) {
	int ans = 1;
	while (b > 0) {
		ans *= a;
		b--;
	}
	return ans;
}

int find_multiple(int k, int n, int b) {
	if (n == 1) {
		return k % b;
	}

	if (n % 2 != 0) {
		return ((k % b) * find_multiple(k, n - 1, b)) % b;
	}
	else {
		return (find_multiple(k, n / 2, b) * find_multiple(k, n / 2, b)) % b;
	}
}

string dp[30];
int dp2[30] = { 0 };

void find_dp(int n) {
	for (int i = 3; i <= n; i++) {
		string num = to_string(i);
		int len = num.length();
		for (int j = n - 1; j >= 0; j--) {
			if (dp2[j] == i - 1 - len) {
				dp[i] = dp[j] + "-" + num;
				break;
			}
		}
	}

}



int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	dp[1] = "1";
	dp[2] = "-2";


	int dp3[1000100][3] = { 0 };
	dp3[1][0] = 0;
	dp3[1][1] = 1;
	dp3[1][2] = 1;

	for (int i = 2; i < 1000100; i++) {
		int check = 0;
		int k = find_multiple(10, i, i + 1) - find_multiple(10, i - 1, i + 1) - 1;
		if (k < 0) { k += i + 1; }

		if (dp3[i - 1][0] + dp3[i - 1][1] + dp3[i - 1][2] - 1 > i) {
			int remain = dp3[i - 1][0] + dp3[i - 1][1] + dp3[i - 1][2] - 2 - i;
			if (k <= remain) { k += i + 1; check = 1; }
		}

		if (dp3[i - 1][0] <= k && k <= dp3[i - 1][0] + dp3[i - 1][1] + dp3[i - 1][2] - 1) {
			if (dp3[i - 1][0] <= k && k < dp3[i - 1][0] + dp3[i - 1][1]) {
				dp3[i][1] = dp3[i - 1][1] + 1;
				dp3[i][2] = dp3[i - 1][2];
				if (k == dp3[i - 1][0]) dp3[i][0] = i + 1;
				else {
					if (check == 1) k -= i + 1;
					if (dp3[i - 1][0] >= k) dp3[i][0] = dp3[i - 1][0] - k;
					else  dp3[i][0] = dp3[i - 1][0] + (i - 1) + 2 - k;
				}
			}
			else {
				dp3[i][2] = dp3[i - 1][2] + 1;
				dp3[i][1] = dp3[i - 1][1];
				if (check == 1) k -= i + 1;
				if (dp3[i - 1][0] >= k) dp3[i][0] = dp3[i - 1][0] - k;
				else  dp3[i][0] = dp3[i - 1][0] + (i - 1) + 2 - k;
			}

		}
		else {
			if (check == 1) k -= i + 1;

			if (dp3[i - 1][0] >= k) dp3[i][0] = dp3[i - 1][0] - k;
			else  dp3[i][0] = dp3[i - 1][0] + (i - 1) + 2 - k;
			dp3[i][1] = dp3[i - 1][1];
			dp3[i][2] = dp3[i - 1][2];

		}
		

	}


	
	for (int i = 1; i < 30; i++) {
	   dp2[i] = i;
	}
	int t;
	cin >> t;
	for (int i = 0; i < t; i++) {
	   int a, b, c;
	   cin >> a >> b;

	   if (b < 2 && a * power(10, b) < 21) {
		  find_dp(a * power(10, b));
		  cout << dp[a * power(10, b)] << "\n";
	   }
	   else {
		  string aa, bb, cc;
		  aa = "1-3-5-7-9-12-15-1...";
		  bb = "1-3-5-7-10-13-16-...";
		  cc = "-2-4-6-8-11-14-17...";

		  int dig = (double)log10(a) + b;
		  
		  int tm = ((a % (dig + 2)) * find_multiple(10, b, dig + 2)) % (dig + 2) - find_multiple(10, dig, dig + 2);
		  if (tm < 0)tm += dig + 2;
		  int i = dig + 1;
		  if (dp3[i - 1][0] + dp3[i - 1][1] + dp3[i - 1][2] - 1 > i) {
			  int remain = dp3[i - 1][0] + dp3[i - 1][1] + dp3[i - 1][2] - 2 - i;
			  if (tm <= remain) tm += i + 1;
		  }

		  if (dp3[i - 1][0] <= tm && tm <= dp3[i - 1][0] + dp3[i - 1][1] + dp3[i - 1][2] - 1) {
			  if (dp3[i - 1][0] <= tm && tm < dp3[i - 1][0] + dp3[i - 1][1])cout << bb << "\n";
			  else cout << cc << "\n";
		  }
		  else cout << aa << "\n";


	   }
	}
	
	


	return 0;

}

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

문제

문제

출처

ICPC

메모리 초과가 뜨는데 혹시 개선방안이 있을까요..

o9j8w7 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말