글 읽기 - 1914번 하노이탑 메모리초과 질문입니다

ericppp 1년 전 0

메모리초과가 뜨는데, 왜 뜨는지 이해가 안갑니다...

하노이탑의 과정을 출력하는 부분은 다른 문제에서 정답이 떴어서 괜찮은 것 같은데

아무래도 hanoi_res_it에 문제가 있는듯합니다. 그런데 이유를 모르겠습니다.

동적할당으로 메모리를 그렇게 많이 쓰는 것 같지 않은데,,, 원인알려주시면 감사하겠습니다.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int hanoi_res_it(int height){	//long long 범위를 벗어나는 값계산 가능하게
	int size = 0;
	int ob,n_ob,carry = 0;
	char* num = (char*)malloc(sizeof(char)*2);
	
	for(int i = 0; i < height; i++){
		if(i == 0)
			strcpy(num, "1");
		else{
			size = strlen(num);   
			for(int j = size - 1; j >= 0; j--){
				ob = (int)(*(num + j)) - 48; 				//ascii
				ob = ob * 2 + carry;
				if( j == size - 1)							//첫재자리에 + 1;
					ob += 1;
				n_ob = ob % 10;
				carry = ob / 10;
				*(num + j) = (char)(n_ob + 48);
			}
			if(carry == 1)									//자릿수 증가
			{
				char* mid = (char*)malloc(sizeof(char)*(size + 2));	//need some check
				num = (char*)realloc(num,sizeof(char)*(size + 2));
				strcpy(mid, "1");
				strcat(mid,num);
				strcpy(num,mid);
				free(mid);
			}
			carry = 0;
		}
	}
	printf("%s\n",num);
	free(num);
	
}

int hanoi_proc(int height, int start, int target){
	if(height==1){
		printf("%d %d\n",start,target);
		return 0;
	}
    else if(height <= 0)
		return 0;
	
	int mid_station = (6-start)-target;
	
	hanoi_proc(height-1,start,mid_station);		//f(n-1)개를 1에서 2로 옮김
	printf("%d %d\n",start,target);				//제일 밑부분을 1에서 3으로 옮김
	hanoi_proc(height-1,mid_station,target);	//f(n-2)개를 2에서 1로 옮김

	return 0;
}

int main(){
	int height;								// 1<=height<=100
	scanf("%d",&height);
	hanoi_res_it(height);		
	if(height<=20)
		hanoi_proc(height,1,3);
	return 0;
}

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

문제

문제

출처

ICPC

1914번 하노이탑 메모리초과 질문입니다

ericppp 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말