글 읽기 - 금민수의 합 문제(다이나믹) 런타임 에러 무엇이 문제인지 모르겠습니다.

juhyun16 6년 전 0

1530 금민수의 합 문제 풀고 있습니다. 런타임 에러가 발생하네요. 무엇이 문제인지 잘 모르겠습니다. 도와주시면 감사하겠습니다.

제가 짠 소스 대략 설명드리겠습니다.

재귀함수를 만들었습니다.

void dfs(int num, vector<int> &v);

지금 현재 단계에서 num이라는 숫자를 금민수로 만들 수 있는지 확인하는 함수이고 이 때 num이 4보다 크면 4부터 vector에 push_back() 해봅니다. 만약 답이 구해지지 않았다면 pop() 하고 이번엔 숫자 7을 push_back() 합니다. 혹시 제가 생각한 로직이 잘못되었을 수도 있을까요??

#include <iostream>
#include <vector>
using namespace std;
bool flag=false;
void dfs(int num, vector<int> &v);
int main(int argc, char* argvp[])
{	
	int N;
	scanf("%d", &N);
	vector<int> v;
	if(N<4)	
	{
		printf("-1\n");
		return 0;
	}
	dfs(N, v);
	if(!flag)
		printf("-1\n");
	else
	{
		int num4=0;
		int num7=0;
		for(vector<int>::iterator itr = v.begin(); itr!=v.end(); itr++)
		{
			if((*itr) == 4)	
				num4++;
			else
				num7++;
		}
		int temp = num4;
		num4 = (num4%7);
		num7 = num7 + ((temp/7)*4);
		while(num4--)
			printf("4 ");
		while(num7--)
			printf("7 ");
		printf("\n");
	}
	return 0;
}
void dfs(int num, vector<int> &v)
{
	if(num==0)
	{
		flag=true;
		return;
	}

	if(num<4)
		return;

	if(!flag)
	{
		v.push_back(4);
		dfs(num-4, v);
		if(!flag)
			v.pop_back();
	}

	if(!flag)
	{
		v.push_back(7);
		dfs(num-7, v);
		if(!flag)
			v.pop_back();
	}
}

bupjae 6년 전 0

n이 최대값에 가까울 때 이 프로그램의 재귀 깊이는 최대 약 2억 5천 단계에 달합니다. 이 정도 재귀를 다룰 수 있는 충분한 메모리를 가지는 컴퓨터는 찾기 힘들 겁니다.

그 전에 문제 이해를 잘못하신 것 같습니다. "4와 7로만 이루어진 수의 합"으로 나타내라고 했으니 4, 7 뿐만이 아니라 44, 47, 74, 77, 444, 447, ... 등을 모두 쓸 수 있습니다.

juhyun16 6년 전 0

아, 그렇군요. 답변 감사합니다~

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

문제

문제

출처

ICPC

금민수의 합 문제(다이나믹) 런타임 에러 무엇이 문제인지 모르겠습니다.

juhyun16 6년 전 0

bupjae 6년 전 0

juhyun16 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말