글 읽기 - c++ 메모리 초과, 조건 이상으로 생각한 풀이.

dlgusrb3456 2년 전 0

이 문제는

2 28

과 같은 경우는 입력으로 주어지지 않지만 이런 경우까지 주어진다는 가정 하에 문제를 풀이하였습니다.

아래의 소스코드로 제출을 하면 72프로 가량에서 메모리 초과가 납니다.

메모리를 사용하는 부분중 하나인 stack에 너무 많은 값이 할당되어 메모리를 초과하는 것인가요?

#include <iostream>
#include <stack>
#include <vector>
using namespace std;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int coins, money;
	cin >> coins >> money;
	vector<int> c;
	for (int i = 0; i < coins; i++) {
		int coin;
		cin >> coin;
		c.push_back(coin);
	}
	stack<pair<int,int>> stk;
	for (int i = coins-1; i >= 0; i--) {
		while (c[i] <= money) {
			money -= c[i];
			stk.push(make_pair(c[i],i));
		}
		if (money <= 0) {
			break;
		}
	}
	if (money == 0) {
		cout << stk.size();
	}
	else {
		int a = stk.size();
		int plussize = 0;
		for (int i = 0; i < a; i++) {
			money += stk.top().first;
			if (stk.top().second - 1 >= 0) {
				int nums = stk.top().second - 1;
				for (int j = nums; j >= 0; j--) {
					if (money % c[j] == 0) {
						plussize = money / c[j];
						break;
					}
				}
			}
			stk.pop();
		}
		cout << stk.size() + plussize;
	}
}

circlezer0 2년 전 0

1 100000000

의 경우

stack 안에 1이 1억개 들어가게 되어 1억 * 4바이트 = 400메가바이트로 메모리초과가 날 수 있습니다.

dlgusrb3456 2년 전 0

감사합니다!

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

문제

문제

출처

ICPC

c++ 메모리 초과, 조건 이상으로 생각한 풀이.

dlgusrb3456 2년 전 0

circlezer0 2년 전 0

dlgusrb3456 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말